data structures - decisiones - Calcule el valor de Hilbert de un punto para usar en un Hilbert R-Tree?

r tree applications

Question

Tengo una aplicación donde 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, hasta donde puedo ver, ninguna de las descripciones de los algoritmos para esta estructura de datos menciona siquiera cómo calcular realmente el valor de Hilbert requerido; que es la distancia a lo largo de una Curva de Hilbert 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.

La potencialmente mala noticia es que está en Haskell ...

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

También propone una métrica de distancia de Lebesgue que podría calcular más fácilmente.

Answer 2

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 el 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 de coincidencia parcial, es decir, consultas que omiten uno o más discriminantes. Solo busca ambas ramas en niveles con un discriminante omitido).

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

Answer 3

Ver uzaygezen .

Answer 4

Miguel,

gracias por tu código 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 5

El código y el código de Java anteriores están bien para los puntos de datos 2D. Pero para dimensiones más grandes puede que necesite mirar el artículo de Jonathan Lawder: JKLawder. Cálculo de asignaciones entre uno y valores n-dimensionales utilizando la curva de relleno de espacio de Hilbert.

Answer 6

Descubrí una forma un poco más eficiente de intercalar bits. Se puede encontrar en el sitio web de gráficos de Stanford . 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, las variables locales B y S deben ser constantes de clase, pero se dejó así por simplicidad.

Answer 7

A continuación se muestra mi código de Java adaptado del código C en el documento "Codificación y decodificación de la orden de Hilbert" por Xian Lu y Gunther Schrack, publicado en Software: Practice and Experience vol. 26 pp 1335 - 46 (1996).

Espero que esto ayude. Mejoras bienvenidas!

Miguel

/**
 * 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 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 usa 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

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

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