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.
Como un simple ejemplo de Fractional Cascading, considere el siguiente problema. Se nos ha dado como entrada un conjunto de k listas ordenadas Li de números reales, de manera que la longitud total Σ|Li| 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,
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 Li. 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. 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 L1[1] = 6.4, L2[3] (un valor mayor que la longitud de la lista indica que q no aparece en L2), L3[2] = 6.2, y L4[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 Mi. La lista final de esta secuencia, Mk, es igual a Lk; cada lista anterior Mi se forma por la fusión de Li con los elementos de las posiciones impares de Mi + 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 Li y la posición resultante de la búsqueda de x en Mi + 1. 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]. El "1" en 6.4[1,5], nos dice que la búsqueda q en L1 debe devolver L1[1] = 6.4. El "5" en 6.4[1,5] nos dice que la ubicación aproximada de q en M2 es la 5. Para ser más preciso, la búsqueda binaria de q en M2 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 M2 es 6.2[3, 3]. El primer "3" en 6.2[3, 3] que la búsqueda de q en L2 debe devolver L2[3], indicando que q no aparece en L2. El segundo "3" en 6.2[3, 3] nos dice que la posición aproximada de q en M3 es la 3. Más precisamente, la búsqueda binaria de q en M3 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 M3 es 6.2[2,3]. El "2" en 6.2[2,3] nos dice que la búsqueda de q en L3 debe devolver L3[2] = 6.2, y el "3" en 6.2[2,3] el resultado de buscar q en M4 es M4[3] = 7.9[3,0] o M4[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 L4 es L4[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 M1 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 M1, y la determinación del valor resultante de la posición de q en L1. Luego, para cada i > 1, se utiliza la posición conocida de q en Mi para encontrar su posición en Mi + 1. El valor asociado con la posición de q en Mi apunta a la posición en Mi + 1 que es el mismo resultado de la búsqueda de q en Mi + 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 Mi en esta estructura de datos es a lo sumo
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
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.
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 .
Escribe un comentario o lo que quieras sobre Algoritmo Fractional Cascading (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)