Caché olvidado kd-Tree

Las estructuras de datos kd-tree ajenas a la memoria caché son una gran utilidad que realiza búsquedas de rango ortogonal multidimensional. Uno de los términos más destacados de los árboles kd es la partición del espacio binario que subdivide periódicamente el espacio en dos conjuntos convexos mediante el uso de hiperplanos como división.

Este artículo se centra en discutir los siguientes temas en detalle: 

1. Caché Olvidado kd-tree.
2. Diseño de Van Emde Boas.
3. Operación en el árbol kd de Cache Oblivious.
4. Ventajas de Cache Oblivious kd-tree.
5. Limitaciones de Cache Oblivious kd-tree.

Caché-Oblivious kd-tree

• El árbol kd ajeno a la memoria caché responde consultas y actualizaciones en una determinada transferencia de memoria.
• La estructura se puede ampliar para admitir consultas de rango d-dimensional con el mismo límite de actualización.
• Para avanzar en la estructura, se utilizan algunas estructuras ajenas a la memoria caché, como el diseño de van Emde Boas y los árboles de búsqueda exponencial.
• El kd-tree propuesto por Jon Louis Bentley es un árbol binario de altura O(log ₂ N) con los N puntos guardados en las hojas del árbol. Los Nodes internos (que también son subárboles) muestran una descomposición periódica del plano mediante líneas ortogonales al eje que dividen el conjunto de puntos en dos subconjuntos de igual tamaño.
• En los niveles pares del árbol, las líneas divisorias son horizontales y en los niveles impares son verticales. De esta manera, una región rectangular A _v se relaciona espontáneamente con cada Node v, y los Nodes en cualquier nivel distinto del árbol dividen el plano en regiones disjuntas. Hay algunos agregadores para decidir qué valor va al eje x y al eje y del plano, si por una razón específica se elige el eje x, todos los puntos menores que x irán al subárbol izquierdo y todos los puntos son mayores que x irá al subárbol derecho.

Diseño de Van Emde Boas 

• El diseño de Van Emde Boas es la mejor forma de establecer un árbol balanceado en la memoria, de modo que una ruta raíz-hoja se pueda recorrer de manera efectiva en el modelo de caché-olvido.
• VEB tiene las propiedades para dar acceso al funcionamiento de un arreglo asociado. Como Insertar, Eliminar, Buscar, Buscar siguiente, Buscar anterior, que luego se utilizan para diseñar los pares clave-valor en la memoria.
• Van Emde Boas observó que si las claves se regulan al conjunto {1, 2, 3, …, n} entonces todas las operaciones se pueden realizar en el tiempo O(log log n) y el espacio O(n).

Operación en caché olvidado kd-tree

Esta sección se enfoca en discutir las tres operaciones en Cache Oblivious kd-tree-

1. Inserción
2. consultando
3. Supresión

Analicemos cada una de estas operaciones en detalle.

1. Inserción:

Con la ayuda del diseño de Van Emde Boas, se dilucida un diseño exponencial. En este diseño, un árbol binario equilibrado T con N hojas se descompone recursivamente en un conjunto de componentes, cada uno de los cuales se presenta utilizando la propiedad INSERT del diseño de Van Emde Boas .

Supongamos para el análisis de la estructura que N es de la forma 22 ^ C, C aquí es un número entero no negativo.

• Formato de memoria: La forma de nivel de grado de diseñar un árbol binario equilibrado es el diseño de Van Emde Boas. La ruta raíz-hoja en este diseño puede atravesar sistemáticamente en el modelo de olvido de caché.

Un árbol binario T de altura O (log ₂ N) con N hojas se puede colocar en O (N) ubicaciones de memoria adyacentes, de modo que cualquier ruta de hoja de raíz se puede atravesar en memoria caché sin darse cuenta en transferencias de memoria O (logN) .

• En este diseño, un árbol binario equilibrado T con N hojas se descompone recursivamente en un conjunto de componentes, cada uno de los cuales se presenta utilizando el diseño de Van Emde Boas. Definimos el componente C ₀ para que consista en los primeros 1/2 log ₂ N niveles de   T . C ₀ contiene Θ(√N) Nodes y se llama componente N porque su raíz es la raíz de un árbol (T) con N hojas.
• El objetivo es adquirir el diseño exponencial de T , utilizando el diseño de Van Emde Boas.
• En primer lugar, almacene C ₀ utilizando el diseño de van Emde Boas, acompañado inmediatamente por el diseño recursivo de los subárboles √N , T ₁ , T ₂ , …, T _√N , de tamaño √N , debajo de C ₀ en T , instruyendo de izquierda a derecha. La recursión se detiene cuando un subárbol tiene 2 hojas; tales 2 componentes se distribuyen en 3 ubicaciones de memoria consecutivas.

• El significado del diseño exponencial define naturalmente una descomposición de T en log ₂ log ₂ N +2 capas, con la capa i que consiste en un número de N ^{1/2^i−1} componentes. Una componente X es de tamaño Θ(√X) y sus hojas √X/2 están conectadas a componentes √X . Por lo tanto, la raíz de un componente X es la raíz de un árbol kd que contiene puntos X.

2. Consulta:

• Considere un diseño exponencial de un árbol binario equilibrado F con W hojas, y sea e la raíz en un subárbol F _e de F que tiene W hojas. Cualquier recorrido de F _e puede realizarse en transferencias de memoria O(1).
• El Node e se almacena dentro de un componente X con F ≤ X ≤ F ² . El componente X tiene un tamaño O(F) y, por lo tanto, se almacena en bloques O(1). Además, la parte de F _e que no está incluida en el componente X se almacena consecutivamente en la memoria en bloques O(1). En consecuencia, la estrategia de paginación óptima puede garantizar que cualquier recorrido de T se realice en transferencias de memoria O(1), simplemente cargando los bloques relevantes de O(1).

¿Cómo se hace la consulta?

• Periódicamente respondemos a una consulta de rango C en un árbol kd Q ajeno a la memoria caché que comienza en la raíz: en un Node e nos movemos a lo largo de la consulta a un hijo e _c de e si C se cruza con la región Re _c asociada con e _c .
• La forma de acotar el número de Nodes en Q visitados al responder a una consulta C, o de manera análoga, el número de Nodes e donde R _e se cruza con C, es primero acotar el número de Nodes e donde R _e se cruza con una línea vertical j .
• La región R _r asociada con la raíz r obviamente es intersecada por j, pero como las regiones asociadas con sus dos hijos representan una subdivisión de R _r con una línea vertical, solo la región Rr _c asociada con uno de estos hijos r _c es intersectada . Debido a que la región Rr _c está subdividida por una línea horizontal, las regiones asociadas con ambos hijos de r _c se intersecan.
• Como cada uno de estos hijos contiene N/4 puntos , la recurrencia del número de regiones intersecadas por j es:

C(N)=2+2C(N/4) = O(√N). 

• En consecuencia, podemos decir que el número de regiones cortadas por una línea horizontal es O(√N) . Significa que el número de regiones intersectadas por el límite de C es O(√N) . El número de Nodes adicionales visitados al responder C está limitado por O(Q), ya que sus regiones correspondientes están completamente contenidas en C. Por lo tanto, en total se visitan O(√N + Q) Nodes.
• Admite actualizaciones en transferencias O (log ₂ N/B · log _M/B N) = O (log ² _B N) . “B” aquí es un bloque de memoria.

3. Eliminación:

• Hay dos invariantes cuando tratamos de eliminar un punto de un árbol kd diseñado utilizando el diseño exponencial relajado. Tenemos que encontrar la hoja W relevante y eliminarla junto con su padre.
• Primera invariante: la eliminación de W puede dar como resultado que esta invariante se contravenga para cada uno de los componentes O (log log N) a lo largo del camino desde la raíz de T hasta W.
• Sea C el componente superior donde se contraviene la Invariante 1.
• Sea V la raíz de C, y sea T _V el subárbol con raíz en V.
• Si T _V es un componente X, entonces contiene X/2 − 1 punto.
• Para restaurar el invariante, primero recolectamos el punto X/2 − 1 en T _V , así como los puntos X/2 ≤ X` ≤ 2X en el subárbol T <sub>V`</sub> , enraizados en el hermano V` de V, y destruimos T <sub>V</sub> , T <sub>V`</sub> , y su padre Y.
• Luego construimos un kd-tree T` en los K puntos recopilados. Si X − 1 ≤ K ≤ 2X, colocamos T` en el espacio previamente ocupado por T _v y T <sub>v`</sub> usando el diseño exponencial, y conectamos el abuelo de v con la raíz de T`.
• En efecto, fusionamos T _v y T _{v`</sub> en T`. Dado que T` contiene entre X − 1 y 2X puntos en el primer caso, y T <sub>U</sub> y T <sub>U`} contienen cada uno entre X y 5X/4 puntos en el segundo caso, podemos en ambos casos diseñar los árboles construidos tal que sus raíces son raíces de una componente X. Por lo tanto, se restaura el Invariante 1.

• La búsqueda de la hoja W requiere transferencias de memoria O(log _{B N).}
• El costo total amortizado de restaurar el primer invariante es:

∑ _i=0 ^{log log N} O( 1/B log _M/B N ^1/2i ) = O( 1/B log _B N) = O(log _B N) transferencias de memoria.

• Segunda invariante:  la eliminación de w puede dar como resultado que esta invariante se viole en los Nodes en el camino desde la raíz de T hasta l.
• Sea v el Node superior donde se contraviene la Invariante 2, y sea K el número de puntos en el subárbol T _v con raíz en v.
• Si v está en un componente X, los subárboles O(√X) T ₁ , … T _{O(√X )} de T _v debajo del componente X que contiene v usan más de una celda de memoria adyacente de 4K.
• El invariante 2 se puede restaurar comprimiendo todos los subárboles.
• Primero, comprima un subárbol Ti _que contenga | T _i | Nodes atravesando T _i y revisando los Nodes en |T _i | celdas de memoria adyacentes. El diseño comprimido de Ti está acompañado inmediatamente en la memoria por el diseño comprimido de _Ti +1 _, empujando efectivamente todo el espacio no utilizado en cada subárbol más allá del final del último subárbol, ahora los subárboles usan menos de 2K celdas de memoria adyacentes e invariantes . 2 está restaurado.

Ventajas de Cache Oblivious kd-tree:

• Durante la construcción del árbol kd, en el modelo RAM, un árbol kd en N puntos puede establecerse periódicamente en tiempo O(N log ₂ N); la línea divisoria de la raíz se encuentra utilizando un algoritmo de mediana de tiempo O(N), los puntos se asignan en dos conjuntos según lo afirmado por esta línea en tiempo O(N), y los dos subárboles se construyen periódicamente.
• La construcción es rápida.

Limitaciones de Cache Oblivious kd-tree:

• Estructuras de datos de búsqueda de rango multidimensional ajenas a la memoria caché, una serie de problemas desafiantes como mejorar el límite de actualización del árbol kd, mejorar el límite de espacio del árbol de rango, eliminar la suposición del tamaño de bloque del árbol de rango.
• Es muy rápido. Sin embargo, puede ser un poco costoso de mantener.

Referencias 

• Árbol de boas de Van Emde
• Estructuras de datos ajenas a la memoria caché para la búsqueda de rango ortogonal
• Estructuras de datos ajenas a la memoria caché