KD-Tree (k-dimensional Tree)

Estructura de datos en árbol de partición espacial para organizar puntos en espacios de baja dimensionalidad.

Tree StructureSpatial PartitioningLow Dimensions

Definición Técnica & Formal

Un KD-Tree divide recursivamente el espacio en hiperplanos alternando a lo largo de las distintas dimensiones. Permite búsquedas rápidas en baja dimensionalidad (D < 20), pero sufre drásticamente de la maldición de la dimensionalidad en embeddings de IA (D >= 768).

Puntos Clave & Aplicaciones

Excelente eficiencia en 2D o 3D (O(log N)).

Degrada a O(N) (igual que KNN) cuando las dimensiones aumentan (D > 20).

Poco utilizado directamente en embeddings modernos de LLMs.

Intuición Visual para Mente Gráfica

"Partir una hoja de papel verticalmente, luego horizontalmente, creando cuadrantes organizados como un mapa de carpetas."

💡 Tip: Puedes presionar el botón "Dibujar / Apuntes" en la barra superior para hacer anotaciones gráficas sobre este diagrama.

Demostración Visual e Interactiva

Interactúa con los controles para simular dinámicamente el funcionamiento de KD-Tree (k-dimensional Tree).

Visualizador de la Arquitectura "KD-Tree (k-dimensional Tree)"

Partir una hoja de papel verticalmente, luego horizontalmente, creando cuadrantes organizados como un mapa de carpetas.

Categoría: Búsqueda Vectorial

Ejemplo de Código & Demostración

python

from scipy.spatial import KDTree
import numpy as np

points = np.random.rand(500, 3) # 500 puntos en 3D
tree = KDTree(points)
distance, index = tree.query([0.5, 0.5, 0.5])
print("Punto más cercano:", points[index])

💡 Construye un árbol KD en 3D y realiza una consulta de vecindad eficiente.

Conceptos Relacionados

KNN (K-Nearest Neighbors)

Búsqueda exacta de los K vecinos más cercanos evaluando exhaustivamente todos los vectores del espacio.

HNSW (Hierarchical Navigable Small World)

Grafo jerárquico multicapa para búsqueda rápida y aproximada de vecinos más cercanos (ANN).

Dimensionalidad & Reducción (Curse of Dimensionality)

El comportamiento paradójico de los espacios de alta dimensión y técnicas para proyectarlos (PCA, t-SNE, UMAP).