Es k-d tree eficiente para la búsqueda kNN. k vecinos más cercanos buscar

Question

Tengo que implementar k vecinos más cercanos buscar 10 datos dimensionales en kd-tree.

Pero el problema es que mi algoritmo es muy rápido para k = 1, pero tanto como 2000x más lenta para k> 1 (k = 2,5,10,20,100)

¿Esto es normal para los árboles kd, o estoy haciendo algo worng?

Answer 1

Bueno, depende principalmente de su implementación particular y conjunto de datos.

Un árbol mal balanceado significa que tendrá que buscar mucho más información de la que necesita. Asegúrate de que la construcción de tu árbol sea sensata.

También podría depender de cómo encuentre los k vecinos. Si su algoritmo busca en el árbol el vecino más cercano y lo almacena, luego busca el segundo más cercano y lo almacena, etc., entonces no está haciendo la búsqueda de manera muy eficiente. En su lugar, mantenga una lista de los k vecinos más cercanos y los puntos de mayor rendimiento fuera de la lista a medida que encuentre más cercanos atravesando el árbol. De esta forma, busca una vez, en vez de k veces.

De cualquier manera, parece que estás haciendo esto para un curso. Intente hablar con su profesor, TA o compañeros de clase para ver si sus resultados son típicos.

Answer 2

Sé que esta pregunta ha sido respondida, pero para más detalles sobre búsquedas KNN con árboles k-d, vea Bentley (1975: 514), Comunicaciones del ACM 18 (9), septiembre.