Hashing 2D, 3D y nD vectores

¿Qué son buenas funciones hash (rápida, buena distribución, pocas colisiones) para hashing 2d y vectores 3d 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.Hashing 2D, 3D y nD vectores

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

Fuente

2011-05-08 Christian Rau

... ¿ha probado qué tan bien se distribuyen sus hash utilizando el método XOR normal? Te sorprenderías. –

@Matti parece que la distribución al menos para los vectores en 3D no es muy mala (probado en conejos de Stanford 35k verts contra tabla hash de tamaño 65537). Solo pensé que alguien quizás tenga una solución más especializada, ya que busqué en la red hace algún tiempo y no he encontrado nada sobre el tema. –

65537 suena como uno más grande que el número que podría querer usar (o es un error tipográfico) –

Hay una función hash espacial descrita en Optimized Spatial Hashing for Collision Detection of Deformable Objects. Ellos usan la función de hash

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

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

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

Fuente

2011-05-08 18:56:48 celion

+14

Tenga en cuenta que 19349663 no es primer (es el producto de 41 y 471943) – sehe

Encontré que el uso de los números primos p1 y p3 para el caso bidimensional resulta en distribuciones muy buenas. – axel22

Cuando escribieron 'x p1 xor y p2 xor z p3', ¿querían decir' (x * p1) xor (y * p2) xor (z * p3) 'o' x * (p1 xor y) * (p2 xor z) * p3'? – emlai

Tengo dos sugerencias.

Supongamos una celda de cuadrícula de tamaño l y cuantizar los x, Y y z coordina mediante el cálculo de ix = floor (x/l), iy = piso (y/l) y iz = floor (z/l), donde ix, iy y iz son enteros. Ahora use la función hash definida en Optimized Spatial Hashing for Collision Detection of Deformable Objects

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

Locality Sensitive Hashing se ha 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 es here.

Fuente

2014-05-05 23:20:59

Respuesta

Cuestiones relacionadas