Calcola il valore di Hilbert di un punto da utilizzare in un R-Tree di Hilbert?

Question

Ho un'applicazione in cui un Hilbert R-Tree (wikipedia) (citeseer) sembrerebbe essere una struttura dati appropriata. In particolare, richiede query spaziali ragionevolmente veloci su un set di dati che subirà molti aggiornamenti.

Tuttavia, per quanto posso vedere, nessuna delle descrizioni degli algoritmi per questa struttura di dati nemmeno menziona come calcolare effettivamente il valore di Hilbert ; che è la distanza lungo una Hilbert Curve al punto.

Qualche suggerimento su come procedere per calcolare questo?

Answer 1

Domanda divertente!

Ho fatto un po 'di ricerche su Google, e la buona notizia è che ho trovato un'implementazione di Hilbert Value.

La notizia potenzialmente negativa è, è in Haskell ...

http : //www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/

Propone inoltre una metrica della distanza di Lebesgue che potresti essere in grado di calcolare più facilmente.

Answer 2

Di seguito è riportato il mio codice java adattato dal codice C nel documento "Codifica e decodifica dell'ordine di Hilbert" di Xian Lu e Gunther Schrack, pubblicato in Software: Practice and Experience Vol. 26 pagg. 1335-46 (1996).

Spero che questo aiuti. Miglioramenti benvenuti!

Michael

/**
 * Find the Hilbert order (=vertex index) for the given grid cell 
 * coordinates.
 * @param x cell column (from 0)
 * @param y cell row (from 0)
 * @param r resolution of Hilbert curve (grid will have Math.pow(2,r) 
 * rows and cols)
 * @return Hilbert order 
 */
public static int encode(int x, int y, int r) {

    int mask = (1 << r) - 1;
    int hodd = 0;
    int heven = x ^ y;
    int notx = ~x & mask;
    int noty = ~y & mask;
    int temp = notx ^ y;

    int v0 = 0, v1 = 0;
    for (int k = 1; k < r; k++) {
        v1 = ((v1 & heven) | ((v0 ^ noty) & temp)) >> 1;
        v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
    }
    hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));

    return interleaveBits(hodd, heven);
}

/**
 * Interleave the bits from two input integer values
 * @param odd integer holding bit values for odd bit positions
 * @param even integer holding bit values for even bit positions
 * @return the integer that results from interleaving the input bits
 *
 * @todo: I'm sure there's a more elegant way of doing this !
 */
private static int interleaveBits(int odd, int even) {
    int val = 0;
    // Replaced this line with the improved code provided by Tuska
    // int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even));
    int max = Math.max(odd, even);
    int n = 0;
    while (max > 0) {
        n++;
        max >>= 1;
    }

    for (int i = 0; i < n; i++) {
        int bitMask = 1 << i;
        int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0;
        int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0;
        val += a + b;
    }

    return val;
}

Answer 3

Vedi uzaygezen .

Answer 4

Il codice e il codice java sopra vanno bene per i punti dati 2D. Ma per dimensioni superiori potrebbe essere necessario consultare l'articolo di Jonathan Lawder: JKLawder . Calcolo delle mappature tra valori unidimensionali e n utilizzando la curva di riempimento dello spazio di Hilbert.

Answer 5

Ho trovato un modo leggermente più efficiente per intercalare i bit. È disponibile nel Sito Web di Stanford Graphics . Ho incluso una versione che ho creato che può intercalare due numeri interi a 32 bit in uno lungo a 64 bit.

public static long spreadBits32(int y) {
    long[] B = new long[] {
        0x5555555555555555L, 
        0x3333333333333333L,
        0x0f0f0f0f0f0f0f0fL,
        0x00ff00ff00ff00ffL,
        0x0000ffff0000ffffL,
        0x00000000ffffffffL
    };

    int[] S = new int[] { 1, 2, 4, 8, 16, 32 };
    long x = y;

    x = (x | (x << S[5])) & B[5];
    x = (x | (x << S[4])) & B[4];
    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];
    return x;
}

public static long interleave64(int x, int y) {
    return spreadBits32(x) | (spreadBits32(y) << 1);
}

Ovviamente, le variabili locali B e S dovrebbero essere costanti di classe ma è stata lasciata così per semplicità.

Answer 6

Michael,

grazie per il tuo codice Java! L'ho provato e sembra funzionare bene, ma ho notato che la funzione di interleaving dei bit trabocca al livello di ricorsione 7 (almeno nei miei test, ma ho usato valori lunghi), perché il valore " n " -value è calcolato usando il più altoOneBit () -funzione, che restituisce il valore e non la posizione del bit più alto; quindi il ciclo fa inutilmente molti intrecci.

L'ho appena cambiato nel seguente frammento, e dopo ha funzionato bene.

  int max = Math.max(odd, even);
  int n = 0;
  while (max > 0) {
    n++;
    max >>= 1;
  }

Answer 7

Se hai bisogno di un indice spaziale con capacità di eliminazione / inserimento rapido, dai un'occhiata all'albero PH. Si basava in parte su quadrifogli ma più veloce e più efficiente in termini di spazio. Internamente utilizza una curva Z che ha proprietà spaziali leggermente peggiori rispetto a una curva H ma è molto più facile da calcolare.

Documento: http://www.globis.ethz.ch/ script / pubblicazione / scaricare? docid = 699

Implementazione Java: http: // globis .ethz.ch / files / 2014/11 / ph-tree-2014-11-10.zip

Un'altra opzione è l'X-tree, che è disponibile anche qui: https://code.google.com/p/xxl/

Answer 8

Suggerimento: una buona struttura dati semplice ed efficiente per le query spaziali è un albero binario multidimensionale.

In un albero binario tradizionale, esiste un "discriminante"; il valore utilizzato per determinare se si prende il ramo sinistro o il ramo destro. Questo può essere considerato il caso monodimensionale.

In un albero binario multidimensionale, hai più discriminanti; livelli consecutivi utilizzano discriminanti diversi. Ad esempio, per i dati spaziali bidimensionali, è possibile utilizzare le coordinate X e Y come discriminanti. I livelli consecutivi utilizzerebbero X, Y, X, Y ...

Per le query spaziali (ad esempio trovare tutti i nodi all'interno di un rettangolo) si esegue una ricerca approfondita dell'albero a partire dalla radice e si utilizza il discriminante a ogni livello per evitare la ricerca di rami che non contengono nodi nella rettangolo dato.

Ciò ti consente di dimezzare potenzialmente lo spazio di ricerca a ogni livello, rendendolo molto efficiente per trovare piccole aree in un set di dati di grandi dimensioni. (A proposito, questa struttura di dati è utile anche per le query a corrispondenza parziale, ovvero query che omettono uno o più discriminanti. Basta cercare entrambi i rami a livelli con un discriminante omesso.)

Un buon documento su questa struttura di dati: http://portal.acm.org /citation.cfm?id=361007 Questo articolo contiene buoni diagrammi e descrizioni dell'algoritmo: http://en.wikipedia.org/wiki/Kd -tree