Árbol PH

El árbol PH ^{[ 1 ]} es una estructura de datos de árbol utilizada para la indexación espacial de datos multidimensionales (claves) como coordenadas geográficas, puntos, vectores de características , rectángulos o cuadros delimitadores . El árbol PH es un índice de partición espacial ^{[ 2 ]} con una estructura similar a la de un quadtree u octree ^{[ 3 ]} . Sin embargo, a diferencia de los quadtrees, utiliza una política de división basada en tries y similar a los árboles de bits Crit , que se basa en la representación de bits de las claves. La política de división basada en bits, cuando se combina con el uso de diferentes representaciones internas para los nodos, proporciona escalabilidad con datos de alta dimensión. La política de división de representación de bits también impone una profundidad máxima, evitando así árboles degenerados y la necesidad de reequilibrio ^{[ 1 ] .}

Descripción general

El árbol PH básico es un índice espacial que asigna claves, que son vectores $d$ -dimensionales con enteros, a valores definidos por el usuario. El árbol PH es una generalización multidimensional de un árbol de bits críticos en el sentido de que un árbol de bits críticos es equivalente a un árbol PH con $1$ Claves dimensionales. Al igual que el árbol de bits Crit, y a diferencia de la mayoría de los demás índices espaciales, el árbol PH es un mapa en lugar de un multimapa . ^{[ 1 ]}^{[ 4 ]}

Un árbol PH $d$ -dimensional es un árbol de nodos donde cada nodo particiona el espacio subdividiéndolo en $2^{d}$ cuadrantes (véase más abajo cómo los nodos potencialmente grandes escalan con datos de alta dimensión). Cada cuadrante contiene como máximo una entrada , ya sea un par clave-valor (cuadrante hoja) o un par clave-subnodo. Para un par clave-subnodo, la clave representa el centro del subnodo. La clave también es el prefijo común (representación de bits) de todas las claves en el subnodo y sus subnodos hijos. Cada nodo tiene al menos dos entradas; de lo contrario, se fusiona con el nodo padre. ^{[ 1 ]}

Algunas otras propiedades estructurales de los árboles PH son: ^{[ 1 ]}

Ellos son $2^{n}$ -arios árboles.
Son inherentemente desequilibrados , pero el desequilibrio es limitado debido a que su profundidad está limitada al ancho de bits de las claves, por ejemplo, a 32 para un $d$ Clave dimensional con enteros de 32 bits.
Las operaciones de inserción o eliminación modifican exactamente un nodo y, potencialmente, añaden o eliminan un segundo. Esto puede resultar útil para implementaciones concurrentes. Además, implica poca variación en el coste de modificación.
Su estructura es independiente del orden de inserción/eliminación.

Estrategia de división

Similar a la mayoría de los quadtrees , el árbol PH es una jerarquía de nodos donde cada nodo divide el espacio en todas $las d$ dimensiones. ^{[ 1 ]} Por lo tanto, un nodo puede tener hasta $2^{d}$ subnodos, uno por cada cuadrante.

Numeración de cuadrantes

El árbol PH utiliza los bits de las claves multidimensionales para determinar su posición en el árbol. Todas las claves que tienen los mismos bits iniciales se almacenan en la misma rama del árbol. ^{[ 1 ]}

Por ejemplo, en un nodo de nivel $L$ , para determinar el cuadrante donde se debe insertar (o extraer o buscar) una clave, se examina el bit $L$ de cada dimensión de la clave. Para un nodo 3D con 8 cuadrantes (que forman un cubo), el bit $L$ de la primera dimensión de la clave determina si el cuadrante de destino está a la izquierda o a la derecha del cubo, el bit $L$ de la segunda dimensión determina si está al frente o en la parte posterior, y el bit L de la tercera dimensión determina si está abajo o arriba (ver imagen) $.$

Ejemplo 1D

Ejemplo con tres claves 1D con valores de 8 bits: $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ , $k_{1}=\{4\}_{10}=\{00000100\}_{2}$ y $k_{2}=\{35\}_{10}=\{00100011\}_{2}$ . Añadiendo $k_{0}$ y $k_{1}$ a un árbol vacío da como resultado un solo nodo. Las dos claves difieren primero en su sexto bit, por lo que el nodo tiene un nivel $L=5$ (comenzando con 0). El nodo tiene un prefijo de 5 bits que representa los 5 bits comunes de ambas claves. El nodo tiene dos cuadrantes, cada clave se almacena en un cuadrante. Añadiendo una tercera clave $k_{3}$ da como resultado un nodo adicional en $L=2$ con un cuadrante que contiene el nodo original como subnodo y el otro cuadrante que contiene la nueva clave. $k_{2}$ .

Ejemplo en 2D

Con claves 2D cada nodo tiene $2^{d}=4$ cuadrantes. La posición del cuadrante donde se almacena una clave se extrae de los bits correspondientes de las claves, un bit de cada dimensión. Los cuatro cuadrantes del nodo forman un hipercubo 2D (los cuadrantes pueden estar vacíos). Los bits que se extraen de las claves forman la dirección del hipercubo. $h$ , para $k_{0}\rightarrow h=\{00\}_{2}$ y para $k_{1}\rightarrow h=\{01\}_{2}$ . $h$ es, en efecto, la posición del cuadrante en el hipercubo del nodo.

Estructura del nodo

El orden de las entradas en un nodo siempre sigue el orden Z. Las entradas en un nodo pueden, por ejemplo, almacenarse en matrices de tamaño fijo de tamaño $2^{d}$ . $h$ es entonces efectivamente el índice de matriz de un cuadrante. Esto permite buscar, insertar y eliminar con $O(1)$ y no hay necesidad de almacenar $h$ . Sin embargo, la complejidad espacial es $O(2^{d})$ por nodo, por lo que es menos adecuado para datos de alta dimensión. ^{[ 1 ]}

Otra solución es almacenar las entradas en una colección ordenada, como matrices dinámicas y/o árboles B. Esto ralentiza las operaciones de búsqueda. $O(\log {n_{node\_entries}})$ pero reduce el consumo de memoria a $O(n_{node\_entries})$ . ^{[ 1 ]}

La implementación original buscaba un consumo mínimo de memoria alternando entre la representación de matrices fijas y dinámicas según cuál utilizara menos memoria. ^{[ 1 ]} Otras implementacionesno cambie dinámicamente sino use matrices fijas para $d\lesssim 4$ , matrices dinámicas para $d\lesssim 8$ y árboles B para datos de alta dimensión.

Operaciones

Las operaciones de búsqueda , inserción y eliminación funcionan de forma muy similar: se encuentra el nodo correcto y, a continuación, se realiza la operación sobre él. Las consultas de ventana y las búsquedas de $k$ vecinos más cercanos son más complejas.

Buscar

La operación Lookup determina si existe una clave en el árbol. Recorre el árbol y comprueba cada nodo si contiene un subnodo candidato o un valor de usuario que coincida con la clave. ^{[ 1 ]}

La función lookup(clave) es entrada ← get_root_entry() // si el árbol no está vacío, la entrada raíz contiene un nodo raíz mientras entrada != NIL && entrada.is_subnode() hacer nodo ← entrada.get_node() entrada ← nodo.get_entry(clave) Entrada de retorno repetida // la entrada puede ser NIL

La función get_entry(key) es nodo ← nodo actual h ← extraer_bits_a_profundidad(clave, nodo.obtener_profundidad()} entrada ← nodo.get_entry_at(h) entrada de retorno // la entrada puede ser NIL

Insertar

La operación Insertar inserta un nuevo par clave-valor en el árbol a menos que la clave ya exista. La operación recorre el árbol como la función Buscar y luego inserta la clave en el nodo. Hay varios casos a considerar: ^{[ 1 ]}

El cuadrante está vacío y podemos simplemente insertar una nueva entrada en el cuadrante y regresar.
El cuadrante contiene una entrada de usuario con una clave idéntica a la nueva entrada. Una forma de gestionar esta colisión es devolver un indicador que señale un error de inserción. Si el árbol se implementa como un multimapa con una colección como entrada del nodo, el nuevo valor se añade a dicha colección.
El cuadrante contiene una entrada (de usuario o de subnodo) con una clave diferente. En este caso, es necesario reemplazar la entrada existente por un nuevo subnodo que contenga tanto la entrada antigua como la nueva.

función insertar(nodo, clave, valor) nivel ← nodo.get_level() // El nivel es 0 para la raíz h ← extraer_bits_en_nivel(clave, nivel) entrada ← nodo.get_entry(h) si entrada == NIL entonces // Caso 1. entrada_nueva ← crear_entrada(clave, valor) nodo.establecer_entrada(h, entrada_nueva) else if !entry.is_subnode() && entry.get_key() == key then // Caso 2. Colisión, ya hay una entrada devolver ← inserción fallida de lo contrario // Caso 3. nivel_diff ← obtener_nivel_de_diferencia(clave, entrada.obtener_clave()) entrada_nueva ← crear_entrada(clave, valor) // nuevo subnodo con entrada existente y nueva entrada subnode_new ← create_node(level_diff, entry, entry_new) nodo.set_entry(h, subnode_new) fin si regresa

Eliminar

La eliminación funciona de forma inversa a la inserción, con la restricción adicional de que cualquier subnodo debe eliminarse si quedan menos de dos entradas. La entrada restante se mueve al nodo padre. ^{[ 1 ]}

Consultas de ventana

Las consultas de ventana son consultas que devuelven todas las claves que se encuentran dentro de un hipercuadro rectangular alineado con los ejes . Se pueden definir como dos puntos de dimensión $d.$ $min$ y $max$ que representan las esquinas "inferior izquierda" y "superior derecha" del cuadro de consulta. Una implementación trivial recorre todas las entradas de un nodo (comenzando por el nodo raíz) y, si una entrada coincide, la agrega a la lista de resultados (si es una entrada de usuario) o la recorre recursivamente (si es un subnodo). ^{[ 1 ]}

La función query(node, min, max, result_list) es para cada entrada ← node.get_entries() hacer si entry.is_subnode() entonces si entry.get_prefix() >= min y entry.get_prefix() <= max entonces consulta(entrada.get_subnode(), min, max, lista_de_resultados) fin si si no si entry.get_key() >= min y entry.get_key() <= max entonces lista_resultados.add(entrada) fin si fin si repetir retorno

Para estimar con precisión la complejidad del tiempo de consulta, el análisis debe incluir la dimensionalidad. $d$ . Recorriendo y comparando todos $n_{nodo\_entries}$ Las entradas en un nodo tienen una complejidad temporal de $O(d\cdot n_{node\_entries})$ porque cada comparación de $d$ -clave dimensional con $min/max$ acepta $O(d)$ tiempo. Dado que los nodos pueden tener hasta $2^{d}$ entradas, esto no se adapta bien al aumento de la dimensionalidad $d$ . Hay varias maneras en que este enfoque puede mejorarse haciendo uso de la dirección del hipercubo $h$ . ^{[ 4 ]}

$altura$ mínima y altura $máxima$

La idea es encontrar los valores mínimos y máximos para las direcciones del cuadrante. $h$ de tal manera que la búsqueda pueda evitar algunos cuadrantes que no se superponen con el cuadro de consulta. $C$ ser el centro de un nodo (esto es igual al prefijo del nodo) y $h_{min}$ y $h_{max}$ ser cadenas de dos bits con $d$ bits cada uno. Además, dejemos el subíndice $i$ con $0\leq i<d$ indicar el $i$ un poco de $h_{min}$ y $h_{max}$ y el $i$ dimensión de $min$ , $max$ y $C$ .

Dejar $h_{min,i}=(min_{i}\leq C_{i})$ y $h_{max,i}=(max_{i}\geq C_{i})$ . $h_{min}$ entonces tiene un ` $1$ ` para cada dimensión donde la mitad "inferior" del nodo y todos los cuadrantes en él no se superponen con el cuadro de consulta. De manera similar, $h_{min}$ tiene un ` $0$ ` para cada dimensión donde la mitad "superior" no se superpone con el cuadro de consulta.

$h_{min}$ y $h_{max}$ Luego presente el más bajo y el más alto. $h$ en un nodo que necesita ser recorrido. Cuadrantes con $h<h_{min}$ o $h>h_{max}$ no se intersecan con el cuadro de consulta. Una demostración está disponible en ^{[ 4 ]} . Con esto, la función de consulta anterior se puede mejorar a:

La función query(node, min, max, result_list) es h_min ← calcular h_min h_max ← calcular h_max para cada entrada ← nodo.get_entries_range(h_min, h_max) hacer [...] repetir retorno

Calculador $h_{min}$ y $h_{max}$ es $O(2d)=O(d)$ Dependiendo de la distribución de los cuadrantes ocupados en un nodo, este enfoque permitirá evitar desde ninguna hasta casi todas las comparaciones de claves. Esto reduce el tiempo promedio de recorrido, pero la complejidad resultante sigue siendo $O(d+d\cdot n_{node\_entries})$ . ^{[ 4 ]}

Compruebe si los cuadrantes se superponen con el cuadro de consulta.

Entre $h_{min}$ y $h_{max}$ Aún puede haber cuadrantes que no se superpongan con el cuadro de consulta. Idea: $h_{min}$ y $h_{max}$ Cada uno tiene un bit para cada dimensión que indica si el cuadro de consulta se superpone con la mitad inferior/superior de un nodo en esa dimensión. Esto se puede utilizar para comprobar rápidamente si un cuadrante $h$ se superpone con el cuadro de consulta sin tener que comparar $d$ Claves dimensionales: un cuadrante $h$ se superpone con el cuadro de consulta si para cada ` $0$ ` bit en $h$ existe un correspondiente ` $0$ ` bit en $h_{min}$ y por cada ` $1$ ` bit en $h$ existe un correspondiente ` $1$ ` bit en $h_{max}$ En una CPU con registros de 64 bits, es posible comprobar la superposición de hasta $64$ claves dimensionales en $O(1)$ . ^{[ 4 ]}

La función is_overlap(h, h_min, h_max) devuelve (h | h_min) & h_max == h // se evalúa como 'verdadero' si el cuadrante y la consulta se superponen .

La función query(node, min, max, result_list) es h_min ← calcular h_min h_max ← calcular h_max para cada entrada ← nodo.get_entries_range(h_min, h_max) hacer h ← entrada.get_h(); Si (h | h_min) & h_max == h entonces // se evalúa como 'verdadero' si el cuadrante y la consulta se superponen. [...] fin si se repite regresar

La complejidad temporal resultante es $O(d+n_{entradas_de_nodo})$ comparado con el $O(d\cdot n_{node\_entries})$ de la iteración completa. ^{[ 4 ]}

Recorra los cuadrantes que se superponen con el cuadro de consulta.

Para dimensiones superiores con nodos más grandes también es posible evitar iterar a través de todos $h$ y en su lugar calcular directamente el siguiente superior $h$ que se superpone con el cuadro de consulta. El primer paso coloca ` $1$ `-bits en un dado $h_{input}$ para todos los cuadrantes que no se superponen con el cuadro de consulta. El segundo paso incrementa el adaptado $h$ y el añadido ` $1$ Los bits `-bits activan un desbordamiento para que se omitan los cuadrantes que no se superponen. El último paso elimina todos los bits no deseados utilizados para activar el desbordamiento. La lógica se describe en detalle en ^{[ 4 ]} . El cálculo funciona de la siguiente manera:

La función increment_h(h_input, h_min, h_max) es h_out = h_input | (~ h_max ) // pre-máscara h_out += 1 // incremento h_out = ( h_out & h_max ) | h_min // post - máscara devolver h_out

Nuevamente, para $d\leq 64$ Esto se puede hacer en la mayoría de las CPU en $O(1)$ . La complejidad temporal resultante para recorrer un nodo es $O(d+n_{superpuestos\_cuadrantes})$ . ^{[ 4 ]} Esto funciona mejor si la mayoría de los cuadrantes que se superponen con el cuadro de consulta están ocupados con una entrada.

$k$ vecinos más cercanos

$Las búsquedas de k$ vecinos más cercanos se pueden implementar utilizando algoritmos estándar.^{[ 5 ]}

Claves de punto flotante

El árbol PH solo puede almacenar valores enteros. Los valores de punto flotante se pueden almacenar fácilmente como enteros convirtiéndolos a este tipo. Sin embargo, los autores también proponen un enfoque sin pérdida de precisión. ^{[ 1 ]}^{[ 4 ]}

Conversión sin pérdidas

La conversión sin pérdida de un valor de punto flotante a un valor entero (y viceversa) sin pérdida de precisión se puede lograr simplemente interpretando los 32 o 64 bits del valor de punto flotante como un entero (con 32 o 64 bits). Debido a la forma en que IEEE 754 codifica los valores de punto flotante, los valores enteros resultantes tienen el mismo orden que los valores de punto flotante originales, al menos para valores positivos. El orden para valores negativos se puede lograr invirtiendo los bits que no son de signo. ^{[ 1 ]}^{[ 4 ]}

Ejemplos de implementación en Java :

long encode ( double value ) { long r = Double.doubleToRawLongBits ( value ) ; return ( r > = 0 ) ? r : r ^ 0x7FFFFFFFFFFFFFFFL ; }

Ejemplos de implementación en C++ :

std :: int64_t encode ( double value ) { std :: int64_t r ; memcpy ( & r , & value , sizeof ( r )); return r >= 0 ? r : r ^ 0x7FFFFFFFFFFFFFFFL ; }

La codificación (y la decodificación inversa) es sin pérdidas para todos los valores de punto flotante. El orden funciona bien en la práctica, incluyendo $\pm \infty$ y $-0.0$ Sin embargo, la representación entera también se convierte en $NaN$ en un valor comparable normal (menor que infinito), los infinitos son comparables entre sí y $0.0$ es más grande que $-0.0$ . ^{[ 6 ]} Eso significa que, por ejemplo, un rango de consulta $[0.0,10.0]$ no coincidirá con un valor de $-0.0$ . Para que coincida $-0.0$ El rango de consulta debe ser $[-0.0,10.0]$ .

Claves de Hyperbox

Para almacenar volúmenes (hipercajas alineadas con los ejes) como claves, las implementaciones suelen utilizar la representación de esquinas ^{[ 7 ]} que convierte los dos $d$ -esquinas mínimas y máximas dimensionales de una caja en una sola llave con $2d$ dimensiones, por ejemplo, intercalándolas: $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ .

Esto funciona trivialmente para operaciones de búsqueda, inserción y eliminación. Las consultas de ventana deben convertirse desde $d$ vectores de dimensión a $2d$ Vectores de dimensión . Por ejemplo, para una consulta de ventana que coincide con todos los cuadros que están completamente dentro del cuadro de consulta, las claves de consulta son: ^{[ 7 ]}^{[ 8 ]}

$k_{min}=\{min_{0},min_{0},min_{1},min_{1},...,min_{d-1},min_{d-1}\}$

$k_{max}=\{max_{0},max_{0},max_{1},max_{1},...,max_{d-1},max_{d-1}\}$

Para una operación de consulta de ventana que coincide con todos los cuadros que se intersecan con un cuadro de consulta, las claves de consulta son: ^{[ 8 ]}

$k_{min}=\{-\infty ,min_{0},-\infty ,min_{1},...,-\infty ,min_{d-1}\}$

$k_{max}=\{max_{0},+\infty ,max_{1},+\infty ,...,max_{d-1},+\infty \}$

Escalabilidad

En dimensiones altas con menos de $2^{d}$ entradas, un árbol PH puede tener solo un nodo, “degenerando” efectivamente en un árbol B con curva de orden Z. Las operaciones de agregar/eliminar/buscar permanecen $O(\log {n})$ y las consultas de ventana pueden usar los filtros de cuadrante . Sin embargo, esto no puede evitar la maldición de la dimensionalidad , para datos de alta dimensión con $d=50$ o $d=100$ Un árbol PH es solo marginalmente mejor que un escaneo completo. ^{[ 9 ]}

Usos

Las investigaciones han reportado operaciones rápidas de agregar/eliminar/coincidencia exacta con conjuntos de datos grandes y de rápida modificación. ^{[ 10 ]} Se ha demostrado que las consultas de ventana funcionan bien, especialmente para ventanas pequeñas ^{[ 11 ]} o conjuntos de datos grandes ^{[ 12 ].}

El árbol PH es principalmente adecuado para uso en memoria. ^{[ 10 ]}^{[ 13 ]}^{[ 14 ]} El tamaño de los nodos (número de entradas) es fijo, mientras que el almacenamiento persistente tiende a beneficiarse de índices con tamaño de nodo configurable para alinear el tamaño del nodo con el tamaño de página en disco . Esto es más fácil con otros índices espaciales, como los árboles R.

Implementaciones

Java: repositorio de GitHub del inventor original.
C++: Repositorio de GitHub del inventor original.
C++: repositorio de GitHub
C++: repositorio de GitHub

Véase también

Enlaces externos

Sitio web de PH-tree con descripción detallada, ejemplos y comparación de rendimiento.

Referencias

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (junio de 2014). " El árbol PH" . Actas de la Conferencia Internacional ACM SIGMOD de 2014 sobre Gestión de Datos . págs. 397–408 . doi : 10.1145/2588555.2588564 . ISBN 9781450323765. S2CID 6862850 . Consultado el 10 de febrero de 2022 .
↑ Kouahla, Z.; Benrazek, A.-E.; Ferrag, MA; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). "Encuesta sobre la indexación de datos de Big IoT: soluciones potenciales, avances recientes y problemas abiertos" . Future Internet . 14 (1): 19. doi : 10.3390/fi14010019 .
↑ Mahmood, AR; Punni, S.; Aref, WG (2018). "Métodos de acceso espaciotemporal: una revisión (2010 – 2017)". Geoinformatica . 23 (1): 1– 36. doi : 10.1007/s10707-018-0329-2 . S2CID 106407322 .
1 2 3 4 5 6 7 8 9 10 Zäschke, Tilmann; Norrie, Moira (2017). "Recorrido eficiente ordenado en Z de índices de hipercubo". Datenbanksysteme für Business, Technologie und Web (Por cierto, 2017) . Apuntes de conferencias en informática. vol. P-265. Bonn: Gesellschaft für Informatik. págs. 465– 484. doi : 10.3929/ethz-a-010802003 . ISBN 9783885796596.
↑ Hjaltason, Gísli R.; Samet, Hanan (junio de 1999). "Navegación por distancia en bases de datos espaciales" . ACM Transactions on Database Systems . 24 (2): 265–318 . doi : 10.1145/320248.320255 . S2CID 10881319. Recuperado el 12 de febrero de 2022 .
↑ IEEE 754 2019 harvnb error: no hay destino: CITEREFIEEE_7542019 ( ayuda )
1 2 Seeger, B.; Kriegel, HP (1988). "Técnicas para el diseño e implementación de métodos eficientes de acceso espacial". Actas de la Conferencia VLDB de 1988: 14.ª Conferencia Internacional sobre Bases de Datos Muy Grandes . 14 : 360.
1 2 Samet, Hanan (2006). Fundamentos de estructuras de datos multidimensionales y métricas . San Francisco: Elsevier/Morgan-Kaufmann. pp. 440–441 , 453–457 . ISBN 0-12-369446-9.
↑ Li, Yan; Ge, Tingjian; Chen, Cindy (2020). "Índices en línea para consultas predictivas de entidades y agregados Top-k en grafos de conocimiento". 2020 IEEE 36.ª Conferencia Internacional sobre Ingeniería de Datos (ICDE) . págs. 1057–1068 . doi : 10.1109/ICDE48307.2020.00096 . ISBN 978-1-7281-2903-7. S2CID 218907333 .
^ Sprenger , Stefan (2019). Procesamiento eficiente de consultas de rango en la memoria principal (Tesis doctoral). Humboldt-Universität zu Berlin. doi : 10.18452/19786 .
↑ Khatibi, A.; Porto, F.; Rittmeyer, JG; Ogasawara, E.; Valduriez, P.; Shasha, D. (agosto de 2017). "Técnicas de preprocesamiento e indexación para consultas de constelaciones en macrodatos". Análisis de macrodatos y descubrimiento de conocimiento (PDF) . Notas de clase en informática. Vol. 10440. págs. 164–172 . doi : 10.1007/978-3-319-64283-3_12 . ISBN 978-3-319-64282-6. S2CID 3857469 .
↑ Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, ET; Neumann, T.; Kemper, A. (2020). "Database Technology". GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons . Vol. 23. OpenProceedings.org. pp. 169– 180. doi : 10.5441/002/edbt.2021.16 .
↑ Wang, S.; Maier, D.; Ooi, B. (2016). "Indexación rápida y adaptativa de datos observacionales multidimensionales" . Actas de la Fundación VLDB . 9 (14): 1683. doi : 10.14778/3007328.3007334 .
^ Herrera, Stiw; da Silva, Larissa Míguez; Reis, Paulo Ricardo; Silva, Anderson; Oporto, Fabio (2021). "Gestión de datos espacio-temporales dispersos en SAVIME: una evaluación del índice del árbol PH" . Anais do XXXVI Simpósio Brasileiro de Bancos de Dados : 337– 342. doi : 10.5753/sbbd.2021.17895 . S2CID 245185935 .

[PH-tree-2014-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (junio de 2014). " El árbol PH" . Actas de la Conferencia Internacional ACM SIGMOD de 2014 sobre Gestión de Datos . págs. 397–408 . doi : 10.1145/2588555.2588564 . ISBN 9781450323765. S2CID 6862850 . Consultado el 10 de febrero de 2022 .

[Kouahla-2022-2] Kouahla, Z.; Benrazek, A.-E.; Ferrag, MA; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). "Encuesta sobre la indexación de datos de Big IoT: soluciones potenciales, avances recientes y problemas abiertos" . Future Internet . 14 (1): 19. doi : 10.3390/fi14010019 .

[Mahmood-2018-3] Mahmood, AR; Punni, S.; Aref, WG (2018). "Métodos de acceso espaciotemporal: una revisión (2010 – 2017)". Geoinformatica . 23 (1): 1– 36. doi : 10.1007/s10707-018-0329-2 . S2CID 106407322 .

[z-ordered-traversal-2017-4] 1 2 3 4 5 6 7 8 9 10 Zäschke, Tilmann; Norrie, Moira (2017). "Recorrido eficiente ordenado en Z de índices de hipercubo". Datenbanksysteme für Business, Technologie und Web (Por cierto, 2017) . Apuntes de conferencias en informática. vol. P-265. Bonn: Gesellschaft für Informatik. págs. 465– 484. doi : 10.3929/ethz-a-010802003 . ISBN 9783885796596.

[kNN-5] Hjaltason, Gísli R.; Samet, Hanan (junio de 1999). "Navegación por distancia en bases de datos espaciales" . ACM Transactions on Database Systems . 24 (2): 265–318 . doi : 10.1145/320248.320255 . S2CID 10881319. Recuperado el 12 de febrero de 2022 .

[IEEE-754-2019-6] IEEE 754 2019 harvnb error: no hay destino: CITEREFIEEE_7542019 ( ayuda )

[Seeger-1988-corner-representation-7] 1 2 Seeger, B.; Kriegel, HP (1988). "Técnicas para el diseño e implementación de métodos eficientes de acceso espacial". Actas de la Conferencia VLDB de 1988: 14.ª Conferencia Internacional sobre Bases de Datos Muy Grandes . 14 : 360.

[Samet-foundations-2006-8] 1 2 Samet, Hanan (2006). Fundamentos de estructuras de datos multidimensionales y métricas . San Francisco: Elsevier/Morgan-Kaufmann. pp. 440–441 , 453–457 . ISBN 0-12-369446-9.

[Li-2020-9] Li, Yan; Ge, Tingjian; Chen, Cindy (2020). "Índices en línea para consultas predictivas de entidades y agregados Top-k en grafos de conocimiento". 2020 IEEE 36.ª Conferencia Internacional sobre Ingeniería de Datos (ICDE) . págs. 1057–1068 . doi : 10.1109/ICDE48307.2020.00096 . ISBN 978-1-7281-2903-7. S2CID 218907333 .

[Spengler-thesis-10] Sprenger , Stefan (2019). Procesamiento eficiente de consultas de rango en la memoria principal (Tesis doctoral). Humboldt-Universität zu Berlin. doi : 10.18452/19786 .

[Khatibi-2017-11] Khatibi, A.; Porto, F.; Rittmeyer, JG; Ogasawara, E.; Valduriez, P.; Shasha, D. (agosto de 2017). "Técnicas de preprocesamiento e indexación para consultas de constelaciones en macrodatos". Análisis de macrodatos y descubrimiento de conocimiento (PDF) . Notas de clase en informática. Vol. 10440. págs. 164–172 . doi : 10.1007/978-3-319-64283-3_12 . ISBN 978-3-319-64282-6. S2CID 3857469 .

[Kipf-2020-12] Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, ET; Neumann, T.; Kemper, A. (2020). "Database Technology". GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons . Vol. 23. OpenProceedings.org. pp. 169– 180. doi : 10.5441/002/edbt.2021.16 .

[Wang-2016-13] Wang, S.; Maier, D.; Ooi, B. (2016). "Indexación rápida y adaptativa de datos observacionales multidimensionales" . Actas de la Fundación VLDB . 9 (14): 1683. doi : 10.14778/3007328.3007334 .

[Herrera-2021-14] Herrera, Stiw; da Silva, Larissa Míguez; Reis, Paulo Ricardo; Silva, Anderson; Oporto, Fabio (2021). "Gestión de datos espacio-temporales dispersos en SAVIME: una evaluación del índice del árbol PH" . Anais do XXXVI Simpósio Brasileiro de Bancos de Dados : 337– 342. doi : 10.5753/sbbd.2021.17895 . S2CID 245185935 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ].

[ 13 ]

[ 14 ]