Búsqueda rápida de vector de diccionario para un vector determinado. Altas dimensiones

Question

Estoy buscando una respuesta que sea escalable, pero para mi propósito específico, tengo un vector de dimensión 48. Esto podría representarse como una matriz de 48 enteros, todos entre 0 y 255.

Tengo un gran diccionario de estos vectores, aproximadamente 25 mil de ellos.

Necesito poder tomar un vector que puede o no estar en mi base de datos, y encontrar rápidamente qué vector de la base de datos está más cercano. Por más cercano, quiero decir en términos de fórmula de distancia tradicional.

Mi código terminará en Python, pero esta es más una pregunta general.

Brute Force es demasiado lento. Necesito una búsqueda de velocidad cercana al diccionario. ¿Alguien tiene una idea?

Answer 1

Otra técnica que serán de utilidad es sensible localidad de hash: http://en.wikipedia.org/wiki/Locality_sensitive_hashing

No es claro por su pregunta si necesita -exact- vecinos más cercanos. Si está contento con devolver un vector que sea aproximadamente el vecino más cercano, existen soluciones más rápidas. Vea aquí (http://www.cs.umd.edu/~mount/ANN/)

Answer 2

Sugeriría implementar un kd-tree en el que puede realizar Nearest neighbour search. El peor tiempo de búsqueda para N puntos en k dimensiones es O(k.N^(1-1/k)), por lo que debe escalar sublinealmente en N.

Si tengo tiempo, volveré a esta respuesta y proporcionaré una explicación menos escueta que la de Wikipedia.

Ya que estás trabajando en Python esta entrada de libro de cocina de Scipy en kdtrees debería ayudar.