Interrogazione efficiente di un albero B + contenente dati multidimensionali

Question

Ho una raccolta di tuple (x,y) di numeri interi a 64 bit che costituiscono il mio set di dati. Ho, ad esempio, trilioni di queste tuple; non è possibile mantenere il set di dati in memoria su qualsiasi macchina sulla terra. Tuttavia, è abbastanza ragionevole memorizzarli su disco.

Ho un archivio su disco (un albero B +) che consente l'interrogazione rapida e simultanea dei dati in una singola dimensione. Tuttavia, alcune delle mie query si basano su entrambe le dimensioni.

esempi di query:

• trova la tupla cui x è maggiore o uguale a un dato valore
• Trova tupla cui x è il più piccolo possibile S.T. è è maggiore o uguale ad un dato valore
• Trova la tupla il cui x è il più piccolo possibile, ad es. è y è inferiore o uguale a un dato valore
• operazioni di manutenzione (inserire alcune tuple, rimuovere alcune tuple)

La cosa migliore che ho trovato sono curve Z-order, ma io non riesco a capire come condurre le domande dato il mio set di dati bidimensionale.

Le soluzioni che non sono accettabili includono una scansione sequenziale dei dati, che potrebbe essere troppo lenta.

Answer 1

Stai dicendo che non si sa come interrogare curve z-order? Il Wikipedia page descrive come si effettuano ricerche di intervallo.

Una curva a z divide lo spazio in rettangoli nidificati, dove ogni bit aggiuntivo nel tasto divide lo spazio a metà. Per cercare 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 

La peggiore prestazione del caso è cattiva, ovviamente. Puoi regolarlo cambiando il modo in cui costruisci l'indice z-order.

Answer 2

Penso che le strutture di dati più appropriate per le vostre esigenze siano R-tree e le sue varianti (R * -tree, R + -tree, Hilbert R-tree). R-tree è simile a B + -tree, ma consente anche query multidimensionali.

Un'altra struttura di dati rilevante è l'albero di ricerca prioritario. Va bene per le query come i tuoi esempi 1 .. 3, ma non molto efficaci se hai bisogno di aggiornamenti frequenti o di un archivio su disco. Per i dettagli vedere this paper o questo libro: "Handbook of Data Structures and Applications" (Capitolo 18.5).

Answer 3

sto lavorando sulla progettazione di una struttura di dati che è essenzialmente un 'impilato' albero B + (o un d + albero dove d è il numero di dimensioni) per i dati multidimensionali. Credo che sarebbe adatto ai tuoi dati perfettamente ed è stato progettato specificamente per il tuo caso d'uso.

L'idea di base è questa:

Ogni dimensione è un albero B + ed è collegato a B + tree del prossimo dimensione. Cerca normalmente la prima dimensione, una volta raggiunta una foglia contiene un puntatore alla radice dell'albero B + successivo che appartiene alla dimensione successiva. Tutto nel secondo albero B + appartiene allo stesso valore x.

Il piano originale era quello di memorizzare solo i valori univoci per ogni dimensione insieme al suo conteggio. Questo impiega un algoritmo di compressione molto semplice (se si può anche chiamarlo così) pur consentendo l'intera serie di dati da rappresentare. Questo schema di dimensioni "collegate" potrebbe consentire di aggiungere ulteriori dimensioni in un secondo momento poiché vengono semplicemente aggiunte allo stack di alberi B +.

totale di inserimento/ricerca/cancellazione del tempo per 2 dimensioni sarebbe qualcosa di simile a questo:

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

dove b è la base di ogni albero B + e carta (x) sarebbe la cardinalità della dimensione x.

Spero che abbia senso. Sto ancora lavorando su un'implementazione, comunque sentiti libero di usare o addirittura di aumentare l'idea.

Answer 4

http://fallabs.com/tokyocabinet/

Tokyo Gabinetto è una libreria di routine per la gestione di un database. Il database è un semplice file di dati contenente i record, ognuno è una coppia di una chiave e un valore. Ogni chiave e valore sono byte seriali con lunghezza variabile. Sia i dati binari che la stringa di caratteri possono essere utilizzati come chiave e valore. Non esiste né il concetto di tabelle di dati né di tipi di dati. I record sono organizzati in tabella hash, albero B + o array a lunghezza fissa.

Tokyo Cabinet è scritto in linguaggio C e fornito come API di C, Perl, Ruby, Java e Lua. Tokyo Cabinet è disponibile su piattaforme con API conformi a C99 e POSIX. Tokyo Cabinet è un software gratuito concesso in licenza sotto Licenza pubblica generale GNU Lesser.

è facile da integrare?