feature - Hashing 2D, 3D y vectores nD

feature hashing

Question

¿Cuáles son las buenas funciones hash (rápida, buena distribución, pocas colisiones) para hash 2d y 3d vectores compuestos de flotadores IEEE de 32 bits. Supongo que hay vectores 3d generales, pero los algoritmos que asumen normales (siempre en [-1,1]) también son bienvenidos. Tampoco temo la manipulación de bits ya que los flotadores IEEE siempre son flotantes IEEE.

Otro problema más general es el hashing de un vector flotante Nd, donde N es bastante pequeño (3-12) y constante, pero no se conoce en el momento de la compilación. Por el momento, tomo estos flotadores como uints y los combino XOR, lo que probablemente no sea la mejor solución.

Answer 1

Hay una función hash espacial descrita en Hashing optimizado espacial para la detección de colisión de objetos deformables . Usan la función hash

hash (x, y, z) = (x p1 xor y p2 xor z p3) mod n

donde p1, p2, p3 son números primos grandes, en nuestro caso 73856093, 19349663, 83492791, respectivamente. El valor n es el tamaño de la tabla hash.

En el documento, x, y, y z son las coordenadas discretizadas; probablemente también puedas usar los valores binarios de tus carrozas.

Answer 2

Tengo dos sugerencias.

• Suponga una celda de cuadrícula de tamaño l y cuantifique las coordenadas x , y y z calculando ix = piso (x / l) , iy = piso (y / l) e iz = piso (z / l) , donde ix , iy e iz son enteros. Ahora usa la función hash definida en Hashing optimizado espacial para la detección de colisiones de objetos deformables

Si no haces la cuantificación, no será sensible a la cercanía (localidad).

• Locality Sensitive Hashing ha sido mencionado para hash vectores de mayor dimensión. ¿Por qué no usarlos también para vectores 3d o 2d? Una variante de LSH que usa la métrica de distancia de Eucledian adaptada (que es lo que necesitamos para los vectores bidimensionales y tridimensionales) se denomina Locality Sensitive Hashing utilizando distribuciones p-stable. Un tutorial muy legible está here .