2. kNN Conceptual: K Vecinos Más Cercanos

Descripción

El algoritmo kNN (k-Nearest Neighbors) es la base conceptual de toda búsqueda por proximidad: dados N vectores, encuentra los K más cercanos a la query. Aquí verás cómo funciona conceptualmente y por qué la búsqueda exhaustiva (revisar todos los vectores) no escala.

---

¿Qué es kNN?

Definición: Dado un vector query, encontrar los K vectores más cercanos (vecinos) en un conjunto de datos.

Ejemplo:

Dataset: 1 millón de vectores (documentos)
Query: "animal doméstico"
K = 10

Resultado: Los 10 documentos con mayor similaridad coseno

---

Búsqueda exhaustiva (fuerza bruta)

Algoritmo:

1. Para cada vector en el dataset:
     Calcular similaridad(query, vector)
2. Ordenar todos los vectores por similaridad
3. Retornar los top-K

Ejemplo con 5 vectores:

Query: [2, 3]

Vectores:
A = [2, 3]   → similaridad = 1.00
B = [3, 4]   → similaridad = 0.99
C = [1, 5]   → similaridad = 0.85
D = [9, 1]   → similaridad = 0.35
E = [0, -2]  → similaridad = -0.12

Top-3: A, B, C ✅

---

Complejidad de búsqueda exhaustiva

Operaciones por query:

• N cálculos de similaridad (N = tamaño del dataset)
• Ordenar N resultados

Complejidad: O(N × d) donde d = dimensionalidad (1536 para OpenAI)

Problemas de escalabilidad:

Dataset	Cálculos por query	Tiempo (estimado)
1,000 vectores	1,000	~1ms ✅
100,000	100,000	~100ms ⚠️
1M	1,000,000	~1s ❌
10M	10,000,000	~10s ❌
100M	100,000,000	~100s ❌

Conclusión: Búsqueda exhaustiva NO escala para millones de vectores.

---

¿Por qué no escala?

Problema 1: Demasiados cálculos

Con 10M vectores y 1536 dimensiones:

10M × 1536 = 15.36 mil millones de operaciones por query

Incluso con hardware rápido, toma segundos.

---

Problema 2: Latencia inaceptable

En producción:

• Búsqueda debe responder en < 100ms (idealmente < 50ms)
• Búsqueda exhaustiva con 10M vectores → 10+ segundos ❌

---

La solución: Búsqueda aproximada

Idea: No revisar TODOS los vectores. Usar estructura de datos inteligente que permite "saltar" a regiones relevantes del espacio.

Trade-off:

• ✅ Mucho más rápido (1000x-10000x)
• ⚠️ Puede perder algunos resultados (~1-5% error)

¿Por qué es aceptable?

Si los "verdaderos" top-10 son:

1. Doc A (score 0.95)
2. Doc B (score 0.94)
3. Doc C (score 0.93)
...
10. Doc J (score 0.85)

Y el índice aproximado retorna:

1. Doc A (score 0.95) ✅
2. Doc B (score 0.94) ✅
3. Doc D (score 0.92) ← Doc C perdido, pero D es casi igual
...
10. Doc K (score 0.84) ← Doc J perdido, pero K es casi igual

Los usuarios no notarían la diferencia (Doc D es casi tan bueno como Doc C).

---

Tipos de índices aproximados

1. HNSW (Hierarchical Navigable Small World)

• Grafo jerárquico
• Muy rápido, ~99% precisión
• Más memoria

2. IVF (Inverted File Index)

• Clustering + búsqueda en clusters
• Rápido, ~95-98% precisión
• Menos memoria

3. LSH (Locality-Sensitive Hashing)

• Hashing especial
• Muy rápido, menor precisión
• Menos usado en producción moderna

Verás cada uno en detalle en cápsulas siguientes.

---

Resumen

Puntos clave:

• kNN: Encontrar K vecinos más cercanos
• Exhaustivo: O(N × d) → No escala a millones
• Aproximado: 1000x más rápido con ~1-5% error
• Trade-off aceptable: Velocidad > perfección para UX

---

Próxima cápsula: 03-search-indexes.md — Tipos de índices, comparación.