Cascada fraccional

En informática , la cascada fraccionaria es una técnica para acelerar una secuencia de búsquedas binarias del mismo valor en una secuencia de estructuras de datos relacionadas. La primera búsqueda binaria en la secuencia toma una cantidad de tiempo logarítmica, 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 la cascada fraccionaria, introducida en dos artículos por Chazelle y Guibas en 1986 (Chazelle y Guibas 1986a; Chazelle y Guibas 1986b), combinó la idea de la cascada, originada en las estructuras de datos de búsqueda de rango de Lueker (1978) y Willard (1978), con la idea del muestreo fraccionario, que se originó en Chazelle (1983). Autores posteriores introdujeron formas más complejas de cascada fraccionaria que permiten que la estructura de datos se mantenga a medida que los datos cambian mediante una secuencia de eventos discretos de inserción y eliminación.

Ejemplo

Como ejemplo simple de cascada fraccionaria, considere el siguiente problema. Se nos da como entrada una colección de listas ordenadas de números, de modo que la longitud total de todas las listas es , y debemos procesarlas para poder realizar búsquedas binarias de un valor de consulta en cada una de las listas. Por ejemplo, con y , ${\displaystyle k}$ ${\displaystyle L_{i}}$ ${\displaystyle \sum _{i}|L_{i}|}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle k}$ ${\displaystyle k=4}$ ${\displaystyle n=17}$

${\displaystyle L_{1}}$= 24, 64, 65, 80, 93

${\displaystyle L_{2}}$= 23, 25, 26

${\displaystyle L_{3}}$= 13, 44, 62, 66

${\displaystyle L_{4}}$= 11, 35, 46, 79, 81

La solución más sencilla para este problema de búsqueda es simplemente almacenar cada lista por separado. Si lo hacemos así, el requisito de espacio es , pero el tiempo para realizar una consulta es , ya que debemos realizar una búsqueda binaria independiente en cada una de las listas. El peor caso para consultar esta estructura se produce cuando cada una de las listas tiene el mismo tamaño , por lo que cada una de las búsquedas binarias involucradas en una consulta lleva tiempo . ${\displaystyle O(n)}$ ${\displaystyle O{\bigl (}k\log(n/k){\bigr )}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n/k}$ ${\displaystyle k}$ ${\displaystyle O{\bigl (}\log(n/k){\bigr )}}$

Una segunda solución permite consultas más rápidas a costa de más espacio: podemos fusionar todas las listas en una única lista grande y asociar con cada elemento de una lista los resultados de la búsqueda de en cada una de las listas más pequeñas . Si describimos un elemento de esta lista fusionada como donde es el valor numérico y , , , y son las posiciones (el primer número tiene la posición 0) del siguiente elemento al menos tan grande como en cada una de las listas de entrada originales (o la posición después del final de la lista si no existe dicho elemento), entonces tendríamos ${\displaystyle k}$ ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle L_{i}}$ ${\displaystyle x[a,b,c,d]}$ ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle x}$

${\displaystyle L}$= 11 [0,0,0,0], 13 [0,0,0,1], 23 [0,0,1,1], 24 [0,1,1,1], 25 [1,1 ,1,1], 26 [1,2,1,1],

35 [1,3,1,1], 44 [1,3,1,2], 46 [1,3,2,2], 62 [1,3,2,3], 64 [1,3, 3,3], 65 [2,3,3,3],

66 [3,3,3,3], 79 [3,3,4,3], 80 [3,3,4,4], 81 [4,3,4,4], 93 [4,3, 4,5]

Esta solución fusionada permite una consulta en el tiempo : simplemente busque en y luego informe los resultados almacenados en el elemento encontrado por esta búsqueda. Por ejemplo, si , al buscar en se encuentra el elemento 62[1,3,2,3], del cual devolvemos los resultados , (un valor de bandera que indica que está más allá del final de ), , y . Sin embargo, esta solución paga una alta penalización en complejidad de espacio: usa espacio ya que cada uno de los elementos en debe almacenar una lista de resultados de búsqueda. ${\displaystyle O(k+\log n)}$ ${\displaystyle q}$ ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle q=50}$ ${\displaystyle q}$ ${\displaystyle L}$ ${\displaystyle L_{1}[1]=64}$ ${\displaystyle L_{2}[3]}$ ${\displaystyle q}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{3}[2]=62}$ ${\displaystyle L_{4}[3]=79}$ ${\displaystyle O(kn)}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle k}$

La cascada fraccionaria permite resolver este mismo problema de búsqueda con límites de tiempo y espacio que satisfacen lo mejor de ambos mundos: tiempo de consulta y espacio . La solución de la cascada fraccionaria es almacenar una nueva secuencia de listas . La lista final de esta secuencia, , es igual a ; cada lista anterior se forma fusionando con cada segundo elemento de . Con cada elemento de esta lista fusionada, almacenamos dos números: la posición resultante de la búsqueda en y la posición resultante de la búsqueda en . Para los datos anteriores, esto nos daría las siguientes listas: ${\displaystyle O(k+\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle M_{i}}$ ${\displaystyle M_{k}}$ ${\displaystyle L_{k}}$ ${\displaystyle M_{i}}$ ${\displaystyle L_{i}}$ ${\displaystyle M_{i+1}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle L_{i}}$ ${\displaystyle x}$ ${\displaystyle M_{i+1}}$

${\displaystyle M_{1}}$= 24 [0, 1], 25 [1, 1], 35 [1, 3], 64 [1, 5], 65 [2, 5], 79 [3, 5], 80 [3, 6], 93 [4, 6]

${\displaystyle M_{2}}$= 23 [0, 1], 25 [1, 1], 26 [2, 1], 35 [3, 1], 62 [3, 3], 79 [3, 5]

${\displaystyle M_{3}}$= 13 [0, 1], 35 [1, 1], 44 [1, 2], 62 [2, 3], 66 [3, 3], 79 [4, 3]

${\displaystyle M_{4}}$= 11 [0, 0], 35 [1, 0], 46 [2, 0], 79 [3, 0], 81 [4, 0]

Supongamos que deseamos realizar una consulta en esta estructura, para . Primero hacemos una búsqueda binaria estándar para in , encontrando el valor 64 [1,5]. El "1" en 64[1,5], nos dice que la búsqueda para in debe devolver . El "5" en 64 [1,5] nos dice que la ubicación aproximada de in es la posición 5. Más precisamente, la búsqueda binaria para in devolvería el valor 79[3,5] en la posición 5, o el valor 62[3,3] un lugar antes. Al comparar con 62, y observar que es más pequeño, determinamos que el resultado de búsqueda correcto en es 62[3,3]. El primer "3" en 62[3,3] nos dice que la búsqueda para in debe devolver , un valor de bandera que significa que está más allá del final de la lista . El segundo "3" en 62[3,3] nos dice que la ubicación aproximada de in es la posición 3. Más precisamente, la búsqueda binaria de in devolvería el valor 62[2,3] en la posición 3, o el valor 44[1,2] un lugar antes. Una comparación de con el valor más pequeño 44 nos muestra que el resultado de búsqueda correcto en es 62[2,3]. El "2" en 62[2,3] nos dice que la búsqueda de in debería devolver , y el "3" en 62[2,3] nos dice que el resultado de la búsqueda de in es 79[3,0] en la posición 3 o 46[2,0] en la posición 2; la comparación con 46 muestra que el resultado correcto es 79[3,0] y que el resultado de la búsqueda de in es . Por lo tanto, hemos encontrado en cada una de nuestras cuatro listas, haciendo una búsqueda binaria en la lista única seguida de una comparación única en cada una de las listas sucesivas. ${\displaystyle q=50}$ ${\displaystyle q}$ ${\displaystyle M_{1}}$ ${\displaystyle q}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{1}[1]=64}$ ${\displaystyle q}$ ${\displaystyle M_{2}}$ ${\displaystyle q}$ ${\displaystyle M_{2}}$ ${\displaystyle q}$ ${\displaystyle M_{2}}$ ${\displaystyle q}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}[3]}$ ${\displaystyle q}$ ${\displaystyle L_{2}}$ ${\displaystyle q}$ ${\displaystyle M_{3}}$ ${\displaystyle q}$ ${\displaystyle M_{3}}$ ${\displaystyle q}$ ${\displaystyle M_{3}}$ ${\displaystyle q}$ ${\displaystyle L_{3}}$ ${\displaystyle L_{3}[2]=62}$ ${\displaystyle q}$ ${\displaystyle M_{4}}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle L_{4}}$ ${\displaystyle L_{4}[3]=79}$ ${\displaystyle q}$ ${\displaystyle M_{1}}$

En términos más generales, para cualquier estructura de datos de este tipo, realizamos una consulta haciendo una búsqueda binaria de en y determinando a partir del valor resultante la posición de en . Luego, para cada , usamos la posición conocida de en para encontrar su posición en . El valor asociado con la posición de en apunta a una posición en que es el resultado correcto de la búsqueda binaria de en o está a un solo paso de ese resultado correcto, por lo que pasar de a requiere solo una única comparación. Por lo tanto, el tiempo total para una consulta es ${\displaystyle q}$ ${\displaystyle M_{1}}$ ${\displaystyle q}$ ${\displaystyle L_{1}}$ ${\displaystyle i>1}$ ${\displaystyle q}$ ${\displaystyle M_{i}}$ ${\displaystyle M_{i+1}}$ ${\displaystyle q}$ ${\displaystyle M_{i}}$ ${\displaystyle M_{i+1}}$ ${\displaystyle q}$ ${\displaystyle M_{i+1}}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle O(k+\log n)}$

En nuestro ejemplo, las listas en cascada fraccionaria tienen un total de 25 elementos, menos del doble del tamaño de la entrada original. En general, el tamaño de en esta estructura de datos es como máximo , como se puede demostrar fácilmente por inducción. Por lo tanto, el tamaño total de la estructura de datos es como máximo , como se puede ver al reagrupar las contribuciones al tamaño total que provienen de la misma lista de entrada . ${\displaystyle M_{i}}$ $${\displaystyle |L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,}$$ $${\displaystyle \sum |M_{i}|=\sum |L_{i}|\left(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots \right)\leq 2n=O(n),}$$ ${\displaystyle L_{i}}$

El problema general

En general, la cascada fraccionaria comienza con un gráfico de catálogo , un gráfico dirigido en el que cada vértice está etiquetado con una lista ordenada. Una consulta en esta estructura de datos consta de una ruta en el gráfico y un valor de consulta 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 ruta. Para el ejemplo simple anterior, el gráfico de catálogo es en sí mismo una ruta, con solo cuatro nodos. Es posible que los vértices posteriores en la ruta se determinen dinámicamente como parte de una consulta, en respuesta a los resultados encontrados por las búsquedas en partes anteriores de la ruta.

Para manejar consultas de este tipo, para un grafo en el que cada vértice tiene como máximo d aristas entrantes y como máximo d aristas salientes para alguna constante d , las listas asociadas con cada vértice se aumentan con 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 la que se aumentan todas las listas permanezca lineal en el tamaño de entrada. Cada elemento en cada lista aumentada almacena con él la posición de ese elemento en la lista no aumentada almacenada en el mismo vértice, y en cada una de las listas vecinas salientes. En el ejemplo simple anterior, d = 1, y aumentamos cada lista con una fracción de 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 más simples en cada vértice sucesivo de la ruta. Si se utiliza una fracción de 1/ r de elementos para aumentar las listas a partir de cada elemento vecino, entonces cada resultado sucesivo de la consulta puede encontrarse dentro de un máximo de r pasos de la posición almacenada en el resultado de la consulta del vértice de la ruta anterior y, por lo tanto, puede encontrarse en tiempo constante sin tener que realizar una búsqueda binaria completa.

Cascada fraccional dinámica

En la cascada fraccionaria dinámica , la lista almacenada en cada nodo del gráfico del catálogo puede cambiar dinámicamente, mediante una secuencia de actualizaciones en las que se insertan y eliminan elementos de la lista. Esto provoca varias dificultades para la estructura de datos.

En primer lugar, cuando se inserta o se elimina un elemento en un nodo del gráfico del catálogo, debe colocarse dentro de la lista aumentada asociada con ese nodo y puede provocar que los cambios se propaguen a otros nodos del gráfico del catálogo. En lugar de almacenar las listas aumentadas en matrices, se deben almacenar como árboles de búsqueda binaria, de modo que estos cambios se puedan manejar de manera eficiente y al mismo tiempo se puedan realizar búsquedas binarias de las listas aumentadas.

En segundo lugar, una inserción o eliminación puede provocar un cambio en el subconjunto de la lista asociada a un nodo que se pasa a los nodos vecinos del gráfico del catálogo. Ya no es factible, en el entorno dinámico, que este subconjunto se elija como los elementos en cada posición d de la lista, para algún d , ya que este subconjunto cambiaría demasiado drásticamente después de cada actualización. En cambio, una técnica estrechamente relacionada con los árboles B permite la selección de una fracción de datos que se garantiza que sea menor que 1/ d , con los elementos seleccionados espaciados con una cantidad constante de posiciones en la lista completa, y de tal manera que una inserción o eliminación en la lista aumentada asociada a un nodo hace que los cambios se propaguen a otros nodos para una fracción de las operaciones que sea menor que 1/ d . De esta manera, la distribución de los datos entre los nodos satisface las propiedades necesarias para que el algoritmo de consulta sea rápido, al tiempo que garantiza que la cantidad promedio de operaciones de árbol de búsqueda binaria por inserción o eliminación de datos sea constante.

En tercer lugar, y lo más importante, la estructura de datos en cascada fraccionaria estática mantiene, para cada elemento x de la lista aumentada en cada nodo del gráfico del catálogo, el índice del resultado que se obtendría al buscar x entre los elementos de entrada de ese nodo y entre las listas aumentadas almacenadas en los nodos vecinos. Sin embargo, esta información sería demasiado costosa de mantener en la configuración dinámica. Insertar o eliminar un único valor x podría hacer que los índices almacenados en un número ilimitado de otros valores cambiaran. En cambio, las versiones dinámicas de la cascada fraccionaria mantienen varias estructuras de datos para cada nodo:

• Una asignación de los elementos de la lista aumentada del nodo a números enteros pequeños, de modo que el orden de las posiciones en la lista aumentada sea equivalente al orden de comparación de los números enteros, y una asignación inversa de estos números enteros a los elementos de la lista. La técnica de mantenimiento del orden de Dietz (1982) permite mantener esta numeración de manera eficiente.
• Una estructura de datos de búsqueda de números enteros, como un árbol de van Emde Boas , para los números asociados con la lista de entrada del nodo. Con esta estructura y la asignación de elementos a números enteros, se puede encontrar de manera eficiente para cada elemento x de la lista aumentada, el elemento que se encontraría al buscar x en la lista de entrada.
• Para cada nodo vecino en el gráfico del catálogo, una estructura de datos de búsqueda de enteros similar para los números asociados con el subconjunto de los datos propagados desde el nodo vecino. Con esta estructura, y la asignación de elementos a enteros, se puede encontrar de manera eficiente para cada elemento x de la lista aumentada, una posición dentro de un número constante de pasos de la ubicación de x en la lista aumentada asociada con el nodo vecino.

Estas estructuras de datos permiten realizar una cascada fraccionaria dinámica en un tiempo de O(log  n ) por inserción o eliminación, y realizar  una secuencia de k búsquedas binarias siguiendo una ruta de longitud k en el gráfico del catálogo en un tiempo O(log n  +  k  log log  n ).

Aplicaciones

Las capas convexas de un conjunto de puntos, parte de una estructura de datos en cascada fraccionaria eficiente para informes de rango de semiplano.

Las aplicaciones típicas de la cascada fraccionaria involucran estructuras de datos de búsqueda de rango en geometría computacional . Por ejemplo, considere el problema del informe de rango de semiplano : es decir, intersecar un conjunto fijo de n puntos con un semiplano de consulta y enumerar todos los puntos en la intersección. El problema es estructurar los puntos de tal manera que una consulta de este tipo pueda responderse de manera eficiente en términos del tamaño de 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 convexos anidados que consisten en la envoltura convexa del conjunto de puntos y las capas convexas construidas recursivamente de los puntos restantes. Dentro de una sola capa, los puntos dentro del semiplano de consulta pueden encontrarse realizando una búsqueda binaria de la pendiente de la línea límite del semiplano entre la secuencia ordenada de pendientes de aristas de polígonos convexos, que conduce al vértice del polígono que está dentro del semiplano de consulta y más alejado de su límite, y luego buscando secuencialmente a lo largo de las aristas del polígono para encontrar todos los demás vértices dentro del semiplano de consulta. El problema de informe de rango completo del semiplano puede resolverse repitiendo este procedimiento de búsqueda comenzando desde la capa más externa y continuando hacia adentro hasta llegar a una capa que está disjunta del semiespacio de consulta. La cascada fraccionaria acelera las búsquedas binarias sucesivas entre las secuencias de pendientes de aristas de polígonos en cada capa, lo que conduce a una estructura de datos para este problema con espacio O( n ) y tiempo de consulta O(log  n  +  h ). La estructura de datos puede construirse en tiempo O( n  log  n ) mediante 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 gráfico del catálogo es solo una ruta.

Otra aplicación de la cascada fraccionaria en las estructuras de datos geométricos se refiere a la ubicación de puntos en una subdivisión monótona, es decir, una partición del plano en polígonos de manera que cualquier línea vertical intersecta cualquier polígono en, como máximo, dos puntos. Como demostraron Edelsbrunner, Guibas y Stolfi (1986), este problema se puede resolver encontrando una secuencia de caminos poligonales que se extiendan de izquierda a derecha a través de la subdivisión y realizando una búsqueda binaria del más bajo de estos caminos que esté por encima del punto de consulta. Probar si el punto de consulta está por encima o por debajo de uno de los caminos se puede resolver como un problema de búsqueda binaria, buscando la coordenada x de los puntos entre las coordenadas x de los vértices del camino para determinar qué borde del camino podría estar por encima o por debajo del punto de consulta. Por lo tanto, cada consulta de ubicación de puntos se puede resolver como una capa externa de búsqueda binaria entre los caminos, cada paso de los cuales realiza a su vez una búsqueda binaria entre las coordenadas x de los vértices. La cascada fraccionaria se puede utilizar para acelerar el tiempo de las búsquedas binarias internas, reduciendo el tiempo total por consulta a O(log  n ) utilizando una estructura de datos con espacio O( n ). En esta aplicación, el gráfico del 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) aplican la cascada fraccional en el diseño de estructuras de datos para el filtrado rápido de paquetes en enrutadores de Internet . Gao et al. (2004) utilizan la cascada fraccional como 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), "Cascada fraccional dinámica sensible a discrepancias, búsqueda de máximos dominados y vecinos más próximos en 2 dimensiones en cualquier métrica de Minkowski" (PDF) , Algorithms and Data Structures, 10th International Workshop, WADS 2007 , Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, págs. 114–126, arXiv : 0904.4670 , doi :10.1007/978-3-540-73951-7_11, ISBN 978-3-540-73948-7, Número de identificación del sujeto  2590335.
• Buddhikot, Milind M.; Suri, Subhash ; Waldvogel, Marcel (1999), "Técnicas de descomposición espacial para conmutación rápida de capa 4" (PDF) , Actas del sexto taller internacional sobre protocolos para redes de alta velocidad VI del IFIP TC6 / IEEE ComSoc TC sobre redes Gigabit , págs. 25–42, archivado desde el original (PDF) el 20 de octubre de 2004.
• Chazelle, Bernard (1983), "Búsqueda de filtros: un nuevo enfoque para la búsqueda de respuestas" (PDF) , Proc. 24 IEEE FOCS.
• Chazelle, Bernard (1985), "Sobre las capas convexas de un conjunto de puntos" (PDF) , IEEE Transactions on Information Theory , 31 (4): 509–517, CiteSeerX  10.1.1.113.8709 , doi :10.1109/TIT.1985.1057060.
• Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Cascada fraccional: I. Una técnica de estructuración de datos" (PDF) , Algorithmica , 1 (1–4): 133–162, doi :10.1007/BF01840440, S2CID  12745042.
• Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Cascada fraccional: II. Aplicaciones" (PDF) , Algorithmica , 1 (1–4): 163–191, doi :10.1007/BF01840441, S2CID  11232235.
• Chazelle, Bernard ; Liu, Ding (2004), "Límites inferiores para búsqueda de intersecciones y cascada fraccional en dimensiones superiores" (PDF) , Journal of Computer and System Sciences , 68 (2): 269–284, CiteSeerX  10.1.1.298.7772 , doi :10.1016/j.jcss.2003.07.003.
• Dietz, F. Paul (1982), "Mantener el orden en una lista enlazada", Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación – STOC '82 , Association for Computing Machinery, págs. 122-127, doi : 10.1145/800070.802184 , ISBN 978-0-89791-070-5, Número de identificación del sujeto  24008786.
• Edelsbrunner, H. ; Guibas, LJ; Stolfi, J. (1986), "Ubicación óptima de puntos en una subdivisión monótona" (PDF) , SIAM Journal on Computing , 15 (1): 317–340, doi :10.1137/0215023.
• Gao, J. ; Guibas, LJ ; Hershberger, J. ; Zhang, L. (2004), "Información en cascada fraccionada en una red de sensores" (PDF) , Actas del 3.er Simposio Internacional sobre Procesamiento de Información en Redes de Sensores (IPSN'04) , págs. 311–319, doi :10.1145/984622.984668, ISBN 978-1-58113-846-7, Número de identificación del sujeto  1033287.
• JaJa, Joseph F.; Shi, Qingmin (2003), Cascada fraccionaria rápida y sus aplicaciones (PDF) , Universidad de Maryland, Informe técnico UMIACS-TR-2003-71.
• Lakshman, TV; Stiliadis, D. (1998), "Reenvío de paquetes basado en políticas de alta velocidad utilizando una correspondencia de rango multidimensional eficiente", Actas de la Conferencia ACM SIGCOMM '98 sobre aplicaciones, tecnologías, arquitecturas y protocolos para la comunicación informática , págs. 203–214, CiteSeerX  10.1.1.39.697 , doi :10.1145/285237.285283, ISBN 978-1-58113-003-4, Número de identificación del sujeto  15363397.
• Lueker, George S. (1978), "Una estructura de datos para consultas de rango ortogonal", Proc. 19th Symp. Foundations of Computer Science , IEEE, págs. 28-34, doi :10.1109/SFCS.1978.1, S2CID  14970942.
• Mehlhorn, Kurt ; Näher, Stefan (1990), "Cascada fraccionada dinámica", Algorithmica , 5 (1): 215–241, doi :10.1007/BF01840386, S2CID  7721690.
• Sen, SD (1995), "Revisión de la cascada fraccionaria", Journal of Algorithms , 19 (2): 161–172, doi :10.1006/jagm.1995.1032.
• Willard, DE (1978), Algoritmos de búsqueda de bases de datos orientados a predicados, tesis doctoral, Universidad de Harvard.
• Yap, Chee; Zhu, Yunyue (2001), "Otra mirada más a la cascada fraccionaria: gráficos B con aplicación a la ubicación de puntos", Actas de la 13.ª Conferencia Canadiense sobre Geometría Computacional (CCCG'01), págs. 173-176.