Árboles k-d para búsqueda espacial

Un árbol binario de búsqueda generalizado a k dimensiones. Consultas de vecino más cercano y de rango particionando el espacio.

Divide el espacio, un eje a la vez

• La raíz corta en x, los hijos en y, los de ellos en x, … (ejes que rotan)
• Corte en la mediana → balanceado, profundidad O(log n), un punto por celda
• Cada nodo = un plano de corte que parte su región en dos
• Construcción O(n log n)

Mira el vecino más cercano + la poda

La consulta ★ está en la esquina. Las líneas = los cortes del árbol. Poda: si la consulta está más lejos de una línea de corte que de su mejor punto, sáltate ese lado completo. Encontró (9,9) visitando 4 de 12 puntos.

La maldición de la dimensionalidad

2D: examina el 0.8% (100× más rápido). 16D: examina el 99.2% — nada mejor que fuerza bruta.

Por qué muchas dimensiones matan la poda

• Las distancias se CONCENTRAN — el más cercano ≈ el más lejano, así que el mejor hasta ahora casi no poda
• Un plano de corte depende de UN eje; la distancia a un punto, de las k → el plano siempre está cerca
• El volumen explota → celdas dispersas, primer candidato malo
• Toda estructura exacta de NN falla a las ~10–20 dims → usa LSH / HNSW (bases de datos vectoriales)

Para llevar

Excelente en pocas dimensiones; una trampa arriba de ~10–20 (solo conjuntos de puntos estáticos). La maldición es POR QUÉ las bases de datos vectoriales usan búsqueda aproximada. Siguiente: reservoir sampling — una muestra justa de un stream infinito.