Calcular el Hilbert valor de un punto para su uso en una Hilbert R-Tree?

StackOverflow https://stackoverflow.com/questions/106237

  •  01-07-2019
  •  | 
  •  

Pregunta

Tengo una aplicación en la que una de Hilbert R-Tree (wikipedia) (citeseer) parece ser una adecuada estructura de datos.Específicamente, se requiere razonablemente rápida consultas espaciales sobre un conjunto de datos que va a experimentar un montón de actualizaciones.

Sin embargo, hasta donde puedo ver, ninguna de las descripciones de los algoritmos para esta estructura de datos, incluso mención cómo calcular el requisito de Hilbert Valor;cual es la distancia a lo largo de un Curva De Hilbert para el punto.

Así que cualquier sugerencia de cómo ir sobre cómo calcular esto?

¿Fue útil?

Solución

Divertido pregunta!

Hice un poco de google, y la buena noticia es que he encontrado una aplicación de Hilbert Valor.

La potencialmente mala noticia es que en Haskell...

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

Se propone también una Lebesgue distancia métrica usted podría ser capaz de calcular más fácilmente.

Otros consejos

A continuación es mi código de java adaptado de código C en el papel "de la Codificación y decodificación de Hilbert de orden" por Xian Lu y Gunther Schrack, publicado en el Software:La práctica y la Experiencia Vol.26 pp 1335-46 (1996).

Espero que esto ayude.Mejoras de bienvenida !

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

Ver uzaygezen.

El código java y el código de arriba están muy bien para 2D puntos de datos.Pero de mayores dimensiones puede que tenga que buscar a Jonathan Lawder del papel: J. K. Lawder.Cálculo de las Asignaciones de Entre Uno y n-dimensional de Valores en el Espacio de Hilbert de llenado de la Curva.

Me imaginé que fuera un poco más eficiente manera de intercalar bits.Se puede encontrar en el Gráficos De Stanford Sitio Web.He incluido una versión que yo crea que puede intercalar dos enteros de 32 bits a 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, la B y S las variables locales deben ser constantes de clase, pero fue dejada de esta manera por la simplicidad.

Michael,

gracias por el código Java!He probado y parece que funciona bien, pero me di cuenta de que el bit intercalado función se desborda en el nivel de recursividad 7 (al menos en mis pruebas, pero he utilizado valores de largo), porque la "n"se calcula el valor de uso de highestOneBit()-función, que devuelve el valor y no la posición de la máxima de bits;así hace el bucle innecesariamente muchas interpolaciones.

Acabo de cambiar a la siguiente fragmento de código, y después de que funcionaba bien.

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

Si usted necesita un índice espacial con fast delete/insert capacidades, tener una mirada en el PH del árbol.Se basa en parte en quadtrees, pero más rápido y con más eficiencia de espacio.Internamente utiliza un Z de la curva que tiene un poco peor propiedades espaciales de un H-curva pero es mucho más fáciles de calcular.

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

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

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

Sugerencia:Una buena sencillo y eficaz estructura de datos para consultas espaciales es multidimensional del árbol binario.

En un tradicional árbol binario, hay un "discriminante";el valor que se utiliza para determinar si usted toma la rama izquierda o a la derecha de la rama.Este puede ser el caso unidimensional.

En un multidimensionales árbol binario, tiene varios discriminantes;niveles consecutivos de uso de diferentes discriminantes.Por ejemplo, para dos dimensiones espacial de los datos, puede utilizar las coordenadas X e y como discriminantes.Niveles consecutivos haría uso de la X, Y, X, Y...

Para consultas espaciales (por ejemplo, encontrar todos los nodos dentro de un rectángulo) que usted hace una búsqueda en profundidad del árbol desde la raíz, y utilizar el discriminante en cada nivel para evitar la búsqueda bajando por las ramas que no contienen nodos en el rectángulo determinado.

Esto le permite potencialmente cortar el espacio de búsqueda en la mitad en cada nivel, por lo que es muy eficiente para la búsqueda de pequeñas regiones en un enorme conjunto de datos.(Por CIERTO, esta estructura de datos es útil también para la parcial coincidencia de las consultas, es decir,las consultas que se omite uno o más discriminantes.Usted acaba de búsqueda de ambas ramas en los niveles con un omitido discriminante.)

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top