Algoritmo Fractional Cascading

En ciencias de la computación , el algoritmo Fractional Cascading es una técnica para acelerar una secuencia de búsquedas binarias para el mismo valor en una secuencia de estructuras de datos relacionados. La primera búsqueda binaria en la secuencia toma una cantidad logarítmica de tiempo, como es estándar para las búsquedas binarias, pero las búsquedas sucesivas en la secuencia son más rápidas. La versión original de Fractional Cascading, presentada en dos artículos por Chazelle y Guibas en 1986 ( Chazelle y Guibas 1986a ; Chazelle y Guibas 1986b ), combinó la idea de la cascada, surgida de las estructuras de datos para búsquedas de rango de Lueker (1978) y Willard (1978), con la idea de muestreo fraccionado, que se originó en Chazelle (1983). Más tarde autores introdujeron formas más complejas de Fractional Cascading que permiten que la estructura de datos se mantenga, como los cambios en los datos por una secuencia de eventos de inserción y eliminación discretos.

Ejemplo

Como un simple ejemplo de Fractional Cascading, considere el siguiente problema. Se nos ha dado como entrada un conjunto de k listas ordenadas L_i de números reales, de manera que la longitud total Σ|L_i| de las listas es n, y debemos procesarlas para que podamos realizar búsquedas binarias para un valor q en cada una de las k listas. Por ejemplo, con k = 4 y n = 17,

L₁ = 2.4, 6.4, 6.5, 8.0, 9.3

L₂ = 2.3, 2.5, 2.6

L₃ = 1.3, 4.4, 6.2, 6.6

L₄ = 1.1, 3.5, 4.6, 7.9, 8.1

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. El peor de los casos para la consulta de esta estructura se produce cuando cada una de las k listas tiene igual tamaño n/k, por lo que cada una de las k búsquedas binarias toma un tiempo de O(log(n/k)).

Una segunda solución permite consultas rápidas a expensas de más espacio: es posible combinar las k listas en una gran lista única L, y asociar a cada elemento x en L una lista de los resultados de la búsqueda de x en cada una de las listas más pequeñas L_i. 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:

L = 1.1[0,0,0,0], 1.3[0,0,0,1], 2.3[0,0,1,1], 2.4[0,1,1,1], 2.5[1,1,1,1], 2.6[1,2,1,1],

3.5[1,3,1,1], 4.4[1,3,1,2], 4.6[1,3,2,2], 6.2[1,3,2,3], 6.4[1,3,3,3], 6.5[2,3,3,3],

6.6[3,3,3,3], 7.9[3,3,4,3], 8.0[3,3,4,4], 8.1[4,3,4,4], 9.3[4,3,4,5]

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. Por ejemplo, si q = 5.0, la búsqueda de q en L devuelve el elemento 6.2[1,3,2,3], de la cual devolvemos los valores L₁[1] = 6.4, L₂[3] (un valor mayor que la longitud de la lista indica que q no aparece en L₂), L₃[2] = 6.2, y L₄[3] = 7.9. Sin embargo, esta solución paga un alto precio por la complejidad espacial: se utiliza el espacio de O(kn) porque cada uno de los n elementos en L debe almacenar una lista de k resultados.

Fractional Cascading permite que este mismo problema de búsqueda sea resuelto con cotas de espacio y tiempo: tiempo de consulta O(log n + k), y espacio O(n). La solución en Fractional Cascading es almacenar una nueva secuencia de listas M_i. La lista final de esta secuencia, M_k, es igual a L_k; cada lista anterior M_i se forma por la fusión de L_i con los elementos de las posiciones impares de M_i + 1 (cada dos elementos). Con cada elemento x en esta lista fusionada, almacenamos dos números: la posición resultante de la búsqueda de x en L_i y la posición resultante de la búsqueda de x en M_i + 1. Para los datos anteriores, esto nos daría las siguientes listas:

M₁ = 2.4[0, 1], 2.5[1, 1], 3.5[1, 3], 6.4[1, 5], 6.5[2, 5], 7.9[3, 5], 8[3, 6], 9.3[4, 6]

M₂ = 2.3[0, 1], 2.5[1, 1], 2.6[2, 1], 3.5[3, 1], 6.2[3, 3], 7.9[3, 5]

M₃ = 1.3[0, 1], 3.5[1, 1], 4.4[1, 2], 6.2[2, 3], 6.6[3, 3], 7.9[4, 3]

M₄ = 1.1[0, 0], 3.5[1, 0], 4.6[2, 0], 7.9[3, 0], 8.1[4, 0]

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 M₁, encontrando el valor 6.4[1,5]. El "1" en 6.4[1,5], nos dice que la búsqueda q en L₁ debe devolver L₁[1] = 6.4. El "5" en 6.4[1,5] nos dice que la ubicación aproximada de q en M₂ es la 5. Para ser más preciso, la búsqueda binaria de q en M₂ devuelve ya sea el valor 7.9[3, 5] en la posición 5, o el valor 6.2[3, 3] una posición anterior. Comparando q con 6.2, y viendo que es menor, determinamos que le resultado correcto de la búsqueda en M₂ es 6.2[3, 3]. El primer "3" en 6.2[3, 3] que la búsqueda de q en L₂ debe devolver L₂[3], indicando que q no aparece en L₂. El segundo "3" en 6.2[3, 3] nos dice que la posición aproximada de q en M₃ es la 3. Más precisamente, la búsqueda binaria de q en M₃ devuelve el valor 6.2[2, 3] en la posición 3, o el valor 4.4[1, 2] una posición anterior. Comparando q con 4.4 nos dice que el resultado correcto de la búsqueda en M₃ es 6.2[2,3]. El "2" en 6.2[2,3] nos dice que la búsqueda de q en L₃ debe devolver L₃[2] = 6.2, y el "3" en 6.2[2,3] el resultado de buscar q en M₄ es M₄[3] = 7.9[3,0] o M₄[2] = 4.6[2,0]; comparando q con 4.6 nos damos cuenta que el resultado correcto es 7.9[3,0] y que el resultado de buscar q en L₄ es L₄[3] = 7.9. Por lo tanto, hemos encontrado q en cada una de nuestras cuatro listas, haciendo sólo una búsqueda binaria en la lista M₁ seguido de sólo una comparación en cada una de las listas sucesivas.

De manera más general, para cualquier estructura de datos de este tipo, se realiza una consulta mediante una búsqueda binaria para q en M₁, y la determinación del valor resultante de la posición de q en L₁. Luego, para cada i > 1, se utiliza la posición conocida de q en M_i para encontrar su posición en M_i + 1. El valor asociado con la posición de q en M_i apunta a la posición en M_i + 1 que es el mismo resultado de la búsqueda de q en M_i + 1 o sólo una posición anterior, de modo que del paso i al i + 1 solo se requiere de una comparación. Por lo tanto, el tiempo total para una consulta es O(log n + k).

En nuestro ejemplo, las listas fraccionadas en cascada tienen un total de 25 elementos, menos de dos veces la de la entrada original. En general, el tamaño de M_i en esta estructura de datos es a lo sumo

${\displaystyle |L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,}$

como puede ser fácilmente demostrado por inducción. Por lo tanto, el tamaño total de la estructura de datos es a lo sumo

${\displaystyle \sum |M_{i}|=\sum |L_{i}|(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots )\leq 2n=O(n),}$

Problema general

En general, Fractional Cascading comienza con un grafo de catálogo, un grafo dirigido en el que cada vértice tiene una lista ordenada. Una consulta en esta estructura de datos consiste en un camino en el grafo y un valor q; la estructura de datos debe determinar la posición de q en cada una de las listas ordenadas asociadas con los vértices de la trayectoria. 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. Cada elemento de cada lista aumentada almacena la posición de ese elemento en la lista no aumentada almacenada en el mismo vértice, y en cada una de las listas de vecinos salientes. En el sencillo ejemplo de arriba, d = 1, y aumentamos cada lista con la fracción 1/2 de los elementos vecinos.

Una consulta en esta estructura de datos consiste en una búsqueda binaria estándar en la lista aumentada asociada con el primer vértice de la ruta de consulta, junto con búsquedas simples en cada vértice sucesivo de la trayectoria. Si se utiliza una fracción 1 /r de elementos para aumentar las listas de cada elemento vecino, a continuación, cada resultado de la consulta sucesiva se puede encontrar dentro de a lo sumo r pasos de la posición almacenada en el resultado de la consulta desde el vértice trayectoria anterior, y por lo tanto puede ser encontrado en un tiempo constante sin tener que realizar una búsqueda binaria completa.

Aplicaciones

Capas convexas de un conjunto de puntos, parte de una eficiente estructura de datos basada en Fractional Cascading para el problema de la intersección entre un conjunto de puntos y un semiplano.

Las aplicaciones típicas de Fractional Cascading implican a las estructuras de datos para la búsqueda de rango en la geometría computacional. Por ejemplo, considere el problema de saber la intersección de un conjunto fijo de n puntos con un semiplano (half-plane range reporting). El problema es estructurar los puntos de tal manera que una consulta de este tipo se puede responder de manera eficiente en términos de tamaño de la intersección h. Una estructura que se puede utilizar para este propósito son las capas convexas del conjunto de puntos de entrada, una familia de polígonos anidados convexos que conforman la envoltura convexa del conjunto de puntos y las capas convexas de forma recursiva construidas de los puntos restantes. Dentro de una sola capa, los puntos dentro del semiplano consulta se pueden encontrar mediante la realización de una búsqueda binaria para la pendiente de la línea frontera del semiplano entre la secuencia ordenada de pendientes de los lados del polígono convexo, dirigiendo la búsqueda hacia el vértice de polígono que está contenido en el semiplano y más alejado de su frontera, y luego buscar secuencialmente entre los lados del polígono para encontrar el resto de los vértices dentro del semiplano consulta. El problema de half-plane range reporting puede ser resuelto mediante la repetición de este procedimiento de búsqueda a partir de la capa más externa y continuando hacia el interior hasta llegar a una capa que es disjunta con el semiplano consulta. Fractional Cascading acelera las sucesivas búsquedas binarias entre las secuencias de pendientes de los lados del polígono en cada capa, dando lugar a una estructura de datos para este problema con el espacio de O(n) y tiempo de consulta de O(log n + h). La estructura de datos puede ser construido en tiempo O (n log n) por un algoritmo de Chazelle (1985 ). Como en nuestro ejemplo, esta aplicación implica búsquedas binarias en una secuencia lineal de listas (la secuencia anidada de las capas convexas), por lo que el grafo de catálogo es sólo un camino.

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. Como Edelsbrunner, Guibas y Stolfi (1986 mostraron), este problema puede ser resuelto mediante la búsqueda de una secuencia de caminos poligonales que se extienden de izquierda a derecha a través de la subdivisión, y la búsqueda binaria para el más bajo de estos caminos que está por encima del punto de consulta. Comprobando que el punto de consulta se encuentra por encima o por debajo de uno de los caminos puede en sí ser resuelto como un problema de búsqueda binaria, en busca de la coordenada x de los puntos entre las coordenadas x de los vértices del camino para determinar qué arista podría estar por encima o por debajo del punto de consulta. Por lo tanto, cada consulta de ubicación de un punto se puede resolver como una capa exterior de búsqueda binaria entre los caminos, cada paso de la que a su vez realiza una búsqueda binaria entre las coorderndas x de los vértices. 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). En este caso el grafo catálogo es un árbol que representa las posibles secuencias de búsqueda de la búsqueda binaria externa.

Más allá de la geometría computacional, Lakshman y Stiliadis (1998) y Buddhikot, Suri y Waldvogel (1999) aplicaron Fractional Cascading en el diseño de estructuras de datos para un rápido filtrado de paquetes en los routers de Internet . Gao et al. (2004 ) usó Fractional Cascading como un modelo para la distribución y recuperación de datos en redes de sensores .

Referencias

• Atallah, Mikhail J.; Blanton, Marina; Goodrich, Michael T.; Polu, Stanislas (2007), «Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any Minkowski metric», Algorithms and Data Structures, 10th International Workshop, WADS 2007, Lecture Notes in Computer Science 4619, Springer-Verlag, pp. 114-126, ISBN 978-3-540-73948-7, doi:10.1007/978-3-540-73951-7_11 ..
• Buddhikot, Milind M.; Suri, Subhash; Waldvogel, Marcel (1999), «Space Decomposition Techniques for Fast Layer-4 Switching», Proceedings of the IFIP TC6 WG6.1 & WG6.4 / IEEE ComSoc TC on on Gigabit Networking Sixth International Workshop on Protocols for High Speed Networks VI, pp. 25-42, archivado desde el original el 20 de octubre de 2004, consultado el 18 de diciembre de 2013 ..
• Chazelle, Bernard (1983), «Filtering search: A new approach to query-answering», Proc. 24 IEEE FOCS ..
• Chazelle, Bernard (1985), «On the convex layers of a point set», IEEE Transactions on Information Theory 31 (4): 509-517, doi:10.1109/TIT.1985.1057060 ..
• Chazelle, Bernard; Guibas, Leonidas J. (1986), «Fractional cascading: I. A data structuring technique», Algorithmica 1 (1): 133-162, doi:10.1007/BF01840440 ..
• Chazelle, Bernard; Guibas, Leonidas J. (1986), «Fractional cascading: II. Applications», Algorithmica 1 (1): 163-191, doi:10.1007/BF01840441 ..
• Chazelle, Bernard; Liu, Ding (2004), «Lower bounds for intersection searching and fractional cascading in higher dimension», Journal of Computer and System Sciences 68 (2): 269-284, doi:10.1016/j.jcss.2003.07.003 ..
• Dietz, F. Paul (1982), «Maintaining order in a linked list», 14th ACM Symp. Theory of Computing, pp. 122-127, ISBN 0-89791-070-2, doi:10.1145/800070.802184 ..
• Edelsbrunner, H.; Guibas, L. J.; Stolfi, J. (1986), «Optimal point location in a monotone subdivision», SIAM Journal on Computing 15 (2): 317-340, doi:10.1137/0215023 ..
• Gao, J.; Guibas, L. J.; Hershberger, J.; Zhang, L. (2004), «Fractionally cascaded information in a sensor network», Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), pp. 311-319, ISBN 1-58113-846-6, doi:10.1145/984622.984668 ..
• JaJa, Joseph F.; Shi, Qingmin (2003), Fast fractional cascading and its applications, Univ. of Maryland, Tech. Report UMIACS-TR-2003-71 ..
• Lakshman, T. V.; Stiliadis, D. (1998), «High-speed policy-based packet forwarding using efficient multi-dimensional range matching», Proceedings of the ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 203-214, ISBN 1-58113-003-1, doi:10.1145/285237.285283 ..
• Lueker, George S. (1978), «A data structure for orthogonal range queries», Proc. 19th Symp. Foundations of Computer Science, IEEE, pp. 28-34, doi:10.1109/SFCS.1978.1 ..
• Mehlhorn, Kurt; Näher, Stefan (1990), «Dynamic fractional cascading», Algorithmica 5 (1): 215-241, doi:10.1007/BF01840386 ..
• Sen, S. D. (1995), «Fractional cascading revisited», Journal of Algorithms 19 (2): 161-172, doi:10.1006/jagm.1995.1032 ..
• Willard, D. E. (1978), Predicate-oriented database search algorithms, Ph.D. thesis, Harvard University ..
• Yap, Chee; Zhu, Yunyue (2001), «Yet another look at fractional cascading: B-graphs with application to point location», Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), pp. 173-176 ..