Algoritmo Fractional Cascading
Como un simple ejemplo de Fractional Cascading, considere el siguiente problema.
Por ejemplo, con k = 4 y n = 17, La solución más simple a este problema de búsqueda es sólo almacenando cada lista por separado.
Si lo hacemos así, la necesidad de espacio es O(n), pero el tiempo para realizar una consulta es O(k log(n/k)), ya que debemos realizar una búsqueda binaria separada en cada una de las k listas.
Si se describe un elemento de esta lista combinada como x[a,b,c,d] donde x is el valor numérico y a, b, c, y d son las posiciones (el primer número tiene posición 0) del próximo elemento mayor o iqual que x en cada una de las listas de entrada(o la longitud de la lista si ese elemento no existe), entonces tendríamos que: Esta solución combinada permite a una consulta en tiempo O(log n + k): basta buscar q en L y luego buscar sobre la lista correspondiente el elemento x resultante.
La solución en Fractional Cascading es almacenar una nueva secuencia de listas Mi.
Para los datos anteriores, esto nos daría las siguientes listas: Supongamos que queremos realizar una consulta en esta estructura, para q = 5.
En primer lugar, hacemos una búsqueda binaria estándar para q en M1, encontrando el valor 6.4[1,5].
En el simple ejemplo anterior, el grafo de catálogo es en sí mismo un camino, con sólo cuatro nodos.
Es posible que los vértices posteriores en la ruta sean determinados dinámicamente como parte de una consulta, en respuesta a los resultados encontrados por las búsquedas en las partes anteriores del camino.
Para controlar las consultas de este tipo, para un grafo en el que cada vértice tiene a lo sumo d aristas entrantes y a lo sumo d aristas salientes para alguna constante d, las listas asociadas con cada vértice son aumentados por una fracción de los elementos de cada vecino saliente del vértice; la fracción debe elegirse para que sea menor que 1 /d, de modo que la cantidad total por el cual todas las listas se aumentan sigue siendo lineal en el tamaño de la entrada.
Otra aplicación de Fractional Cascading en estructuras de datos geométricas es la ubicación del punto en una subdivisión monótona, es decir, una partición del plano en polígonos de tal manera que cualquier línea vertical se interseca con algún polígono en a lo sumo dos puntos.
Fractional Cascading se puede utilizar para acelerar el tiempo de las búsquedas binarias internas, lo que reduce el tiempo total por consulta a O (log n), utilizando una estructura de datos con espacio O (n).
