Consulta eficiente de un árbol B + que contiene datos multidimensionales

Question

Tengo una colección de tuplas (x,y) de enteros de 64 bits que componen mi conjunto de datos. Tengo, digamos, billones de estas tuplas; no es factible mantener el conjunto de datos en la memoria en ninguna máquina en la tierra. Sin embargo, es bastante razonable almacenarlos en el disco.

Tengo una tienda en disco (un B + -tree) que permite la consulta rápida y concurrente de datos en una sola dimensión. Sin embargo, algunas de mis consultas dependen de ambas dimensiones.

ejemplos de consulta:

• encontrar la tupla cuyo x es mayor que o igual que un valor dado
• Encuentra la tupla cuyo x es lo más pequeño posible S.T. es y es mayor o igual que un valor dado
• Encuentra la tupla cuyo x es lo más pequeño posible a.t. se y es menor o igual a un valor determinado
• realizar operaciones de mantenimiento (insertar alguna tupla, eliminar algunos tupla)

La mejor apuesta que he encontrado son curvas de orden Z, pero me parece que no puede averiguar cómo realizar las consultas dado mi conjunto de datos bidimensionales.

Las soluciones que no son aceptables incluyen un escaneo secuencial de los datos, esto podría ser demasiado lento.

Answer 1

¿Estás diciendo que no sabes cómo consultar las curvas de orden z? El Wikipedia page describe cómo realizar búsquedas de rango.

Una z-curve divide su espacio en rectángulos anidados, donde cada bit adicional de la clave divide el espacio por la mitad. Para buscar un punto:

Start with the largest rectangle that might contain your point. 

    Recursively: 

     Create a result set of rectangles  

    For each rectangle in your set   
     If the rectangle is a single point, you are done, it is what you are looking for. 
     Otherwise, divide the rectangle in two (specify one additional bit of the z-curve) 
      If both halves contain a point 
       If one half is better 
        Add that rectangle to your result set of rectangles 
       Otherwise 
        Add both rectangles to your result set of rectangles 
      Otherwise, only one half contains a point 
        Add that rectangle to your result set of rectangles 

    Search your result set of rectangles 

El peor de los casos es malo, por supuesto. Puede ajustarlo cambiando la forma en que construye su índice de orden z.

Answer 2

Creo que las estructuras de datos más adecuadas para sus requisitos son R-tree y sus variantes (árbol *, árbol + árbol Hilbert). R-tree es similar al árbol B +, pero también permite consultas multidimensionales.

Otra estructura de datos relevante es Priority Search Tree. Es bueno para consultas como sus ejemplos 1 .. 3, pero no es muy eficiente si necesita actualizaciones frecuentes o en la tienda en disco. Para más detalles, vea this paper o este libro: "Handbook of Data Structures and Applications" (Capítulo 18.5).

Answer 3

estoy trabajando actualmente en el diseño de una estructura de datos que es esencialmente un 'apilado' B + árbol (o una d + d árbol donde es el número de dimensiones) para los datos multidimensionales. Creo que se adaptaría perfectamente a sus datos y está diseñado específicamente para su caso de uso.

La idea básica es la siguiente:

Cada dimensión es un árbol B + y está vinculada a la siguiente dimensión de árbol B +. Busque normalmente en la primera dimensión, una vez que se alcanza una hoja, contiene un puntero a la raíz del siguiente árbol B + que pertenece a la siguiente dimensión. Todo en el segundo árbol B + pertenece al mismo valor x.

El plan original era solo almacenar los valores únicos para cada dimensión junto con su recuento. Esto emplea un algoritmo de compresión muy simple (si es que se puede llamar así) al mismo tiempo que permite que se represente todo el conjunto de datos. Este esquema de dimensiones "vinculadas" podría permitir la adición de dimensiones adicionales más adelante, ya que simplemente se agregan a la pila de árboles B +.

total de inserción/buscar/borrar el tiempo de 2 dimensiones sería algo similar a esto:

log b(card(x)) + log b(card(y)) 

donde b es la base de cada árbol B + y tarjeta (x) sería la cardinalidad de la dimensión x.

Espero que tenga sentido. Todavía estoy trabajando en una implementación, sin embargo, siéntete libre de usar o incluso aumentar la idea.

Answer 4

http://fallabs.com/tokyocabinet/

Tokio Gabinete es una biblioteca de rutinas para la gestión de una base de datos. La base de datos es un archivo de datos simple que contiene registros, cada uno es un par de claves y un valor. Cada clave y valor son bytes seriales con longitud variable. Tanto los datos binarios como la cadena de caracteres se pueden usar como una clave y un valor. No existe el concepto de tablas de datos ni tipos de datos. Los registros se organizan en tabla hash, árbol B + o matriz de longitud fija.

Tokyo Cabinet está escrito en el lenguaje C y se proporciona como API de C, Perl, Ruby, Java y Lua. Tokyo Cabinet está disponible en plataformas que tienen API conforme a C99 y POSIX. Tokyo Cabinet es un software gratuito licenciado bajo la Licencia Pública General Reducida de GNU.

¿te es fácil incrustar?