Familia de técnicas de hashing diseñadas para que elementos similares tengan alta probabilidad de mapearse al mismo cubo, permitiendo la búsqueda aproximada de vecinos más cercanos y la reducción de dimensionalidad en datos de alta dimensión.

Principio

Construir funciones o familias de hash ajustadas a una métrica de similitud o distancia elegida de modo que la probabilidad de colisión aumente con la similitud; usar múltiples tablas de hash y concatenación de hashes para equilibrar recuperación y selectividad.

Demostración

Recuperación de imágenes: representar imágenes como vectores de características de alta dimensión y usar LSH (por ejemplo, proyecciones aleatorias para similitud coseno o distribuciones p-estables para L2) para colocar vectores similares en los mismos cubos; en la consulta se buscan solo esos cubos para hallar vecinos aproximados rápidamente.

Aplicación incorrecta

Aplicar LSH con una familia de hash desalineada con la métrica real de similitud (por ejemplo, usar LSH para L2 en una tarea de coseno) o apoyarse en una sola tabla de hash esperando vecinos exactos; esto produce bajo recall o muchos candidatos irrelevantes.

Consecuencia

Tiempo de consulta esperado sublineal para búsqueda aproximada de vecinos con compromisos ajustables entre precisión, memoria y coste de consulta; apto para conjuntos de datos a gran escala y alta dimensión donde la búsqueda exacta es prohibitiva.

Inversión

Búsqueda exacta del vecino más cercano que compara la consulta con todos los puntos (fuerza bruta) o estructuras basadas en partición espacial que empeoran en alta dimensión; ambas garantizan exactitud pero a menudo con costes mucho mayores.

Límite

LSH trata vecinos aproximados bajo medidas de similitud específicas y ofrece garantías probabilísticas; no es una reducción de dimensionalidad universal y su efectividad depende de la distribución de los datos y el ajuste de parámetros.

Tensión semántica

Hashing probabilista que preserva localidad (LSH) versus embeddings deterministas o índices basados en árboles: todos buscan acelerar la búsqueda por similitud, pero difieren en garantías, supuestos métricos y robustez frente a la dimensionalidad.

Síntesis

Conjunto de familias de hash aleatorias que amplifican colisiones para elementos similares según una métrica elegida, permitiendo recuperar vecinos aproximados rápidamente al restringir la búsqueda a unos pocos cubos candidatos y aceptar errores probabilísticos.