¿Puedo usar métricas arbitrarias para buscar árboles KD?

Question

Acabo de implementar un kd-tree para hacer búsquedas rápidas en el vecino más cercano. Estoy interesado en jugar con diferentes métricas de distancia que no sean Euclidean distance. Mi comprensión del árbol kd es que la búsqueda veloz del árbol kd no garantiza búsquedas exactas si la métrica no es euclidiana, lo que significa que podría necesitar implementar una nueva estructura de datos y un algoritmo de búsqueda si quiero intentarlo nuevas métricas para mi búsqueda.

Tengo dos preguntas:

1. ¿Si se usa un kd-tree me atan de forma permanente a la Euclidean distance?
2. En caso afirmativo, ¿qué otro tipo de algoritmos debería probar ese trabajo para metrics arbitrario? No tengo mucho tiempo para implementar muchas estructuras de datos diferentes, pero otras estructuras en las que estoy pensando incluyen cover trees y vp-trees.

Answer 1

El vecino más cercano procedimiento de búsqueda descrito en la página de Wikipedia se ha vinculado a duda se puede generalizar a otras métricas de distancia, siempre que se sustituya "hiperesfera" con el objeto geométrico equivalente para la métrica dada, y probar cada hiperplano de cruces con este objeto.

Ejemplo: si utiliza la distancia de Manhattan (es decir, la suma de los valores absolutos de todas las diferencias en los componentes del vector), su hiperesfera se convertiría en un diamante (multidimensional). (Esto es más fácil de visualizar en 2D; si su vecino más cercano está a la distancia x desde el punto de consulta p, cualquier vecino más cercano detrás de un hiperplano diferente debe intersecar una forma de diamante que tenga ancho y alto 2x y centrado en p). Esto puede hacer que la prueba de cruce de hiperplano sea más difícil de codificar o más lenta de ejecutar, sin embargo, el principio general aún se aplica.

Answer 2

No creo que estés atado a la distancia euclidiana, como dice j_random_hacker, probablemente puedas usar la distancia de Manhattan, pero estoy bastante seguro de que estás vinculado a las geometrías que pueden representarse en coordenadas cartesianas. Por lo tanto, no podría usar un árbol kd para indexar un espacio métrico, por ejemplo.