¿Calcula el valor de Hilbert de un punto para usar en un árbol de Hilbert?

Question

Tengo una aplicación donde un Hilbert R-Tree (wikipedia)(citeseer) parece ser una estructura de datos apropiada. Específicamente, requiere consultas espaciales razonablemente rápidas sobre un conjunto de datos que experimentará una gran cantidad de actualizaciones.

Sin embargo, por lo que yo puedo ver, ninguna de las descripciones de los algoritmos para esta estructura de datos aun mención cómo realmente calcular el requisito Hilbert Valor; que es la distancia a lo largo de un Hilbert Curve al punto.

¿Alguna sugerencia sobre cómo hacer para calcular esto?

Answer 1

¡Pregunta divertida!

Hice un poco de googlear, y la buena noticia es que encontré una implementación de Hilbert Value.

El potencialmente malas noticias son, que es en Haskell ...

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

También propone una distancia de Lebesgue métrica que podría ser capaz de calcular con mayor facilidad.

Answer 2

Ver uzaygezen.

Answer 3

Sugerencia: Una buena estructura de datos eficiente simple para consultas espaciales es un árbol binario multidimensional.

En un árbol binario tradicional, hay un "discriminante"; el valor que se usa para determinar si toma la rama izquierda o la rama derecha. Esto se puede considerar como el caso unidimensional.

En un árbol binario multidimensional, tiene múltiples discriminantes; niveles consecutivos usan diferentes discriminantes. Por ejemplo, para datos espaciales bidimensionales, puede usar las coordenadas X e Y como discriminantes. Los niveles consecutivos usarían X, Y, X, Y ...

Para las consultas espaciales (por ejemplo, encontrar todos los nodos dentro de un rectángulo) se hace una búsqueda en profundidad del árbol que comienza en la raíz, y se usa discriminante en cada nivel para evitar buscar ramas que no contengan nodos en el rectángulo dado.

Esto le permite reducir el espacio de búsqueda a la mitad en cada nivel, lo que lo hace muy eficiente para encontrar regiones pequeñas en un conjunto de datos masivo. (Por cierto, esta estructura de datos también es útil para consultas parciales, es decir, consultas que omiten uno o más discriminantes. Solo busca en ambas ramas en niveles con un discriminante omitido)

Un buen documento sobre esta estructura de datos: http://portal.acm.org/citation.cfm?id=361007 Este artículo tiene buenos diagramas y descripciones algoritmo: http://en.wikipedia.org/wiki/Kd-tree

Answer 4

a continuación se muestra el código java adaptada de código C en el periódico "la codificación y decodificación de la orden de Hilbert" de Xian Lu y Gunther Schrack, publicado en software: Práctica y Experiencia Vol. 26 pp 1335 - 46 (1996).

Espero que esto ayude. Mejoras bienvenidas!

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 5

Michael,

gracias por su código de Java! Lo probé y parece funcionar bien, pero noté que la función de entrelazado de bits se desborda en el nivel de recursión 7 (al menos en mis pruebas, pero utilicé valores largos), porque el valor "n" se calcula utilizando highestOneBit () -función, que devuelve el valor y no la posición del bit más alto; por lo que el ciclo hace innecesariamente muchas intercalaciones.

Lo cambié al siguiente fragmento, y después de eso funcionó bien.

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

Answer 6

Descubrí una forma un poco más eficiente para intercalar bits. Se puede encontrar en el Stanford Graphics Website. Incluí una versión que he creado que puede intercalar dos enteros de 32 bits en uno de 64 bits de largo.

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); 
} 

Obviamente, los B y S variables locales deben ser constantes de clase pero se dejó de esta manera por la simplicidad.

Answer 7

El código y el código de java de arriba están bien para los puntos de datos 2D. Pero para dimensiones más grandes, puede necesitar consultar el documento de Jonathan Lawder: J.K.Lawder. Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve.

Answer 8

Si necesita un índice espacial con capacidades de eliminación e inserción rápidas, eche un vistazo al árbol PH. Se basa en parte en quadtrees pero más rápido y más eficiente en el uso del espacio. Internamente utiliza una curva Z que tiene propiedades espaciales ligeramente peores que una curva H, pero es mucho más fácil de calcular.

Papel: http://www.globis.ethz.ch/script/publication/download?docid=699

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

Otra opción es el X-árbol, que también está disponible aquí: https://code.google.com/p/xxl/