La búsqueda de similitud se puede generalizar como búsqueda de vecino más cercano aproximado. Una ingenua exploración lineal basada en algoritmos de búsqueda de similitud es de [matemática] O (N * D) [/ matemática] complejidad. Entonces hay dos formas de mejorar: reducir el número de comparaciones realizadas y acelerar las comparaciones individuales. Por lo tanto, las técnicas de búsqueda rápida de similitud se pueden clasificar en términos generales como:
Partición basada:
- ¿Cómo se imprime el reverso de una pila de objetos iterables?
- ¿Qué sabes sobre el algoritmo de búsqueda de Fiverr?
- ¿Cuál es el "mejor" sitio para estudiar estructuras de datos durante las ubicaciones?
- Cómo resolver este problema de integración definitiva
- ¿Qué es el algoritmo LSH Forest?
Este es uno de los primeros métodos para acelerar la búsqueda de similitud. La técnica implica una búsqueda basada en ramas y enlaces en el espacio de datos. La estructura de indexación suele ser una estructura de datos de árbol. Algunas de las técnicas de indexación comunes son:
- árbol kd: estructura de datos basada en particiones de espacio binario, donde el espacio de datos se divide recursivamente por dimensiones sucesivas. Un enfoque similar es Quadtree, que divide el espacio en cuatro en cada nivel. Hay muchas variantes con árboles KD aleatorios que son la escalable reciente.
- R-tree: esta indexación es adecuada para la búsqueda de vecinos en el espacio 2D. La técnica de indexación implica rectángulos jerárquicos superpuestos. Hay variantes como R + tree, R * tree y X-tree.
- Árbol métrico: estructura de indexación definida en espacios métricos, utilizando algunas de las propiedades como la desigualdad triangular. Uno popular es el árbol M
Para un tratamiento exhaustivo de las técnicas de indexación multidimensional, una de las mejores referencias son Fundamentos de estructuras de datos multidimensionales y métricas de H. Samet. En general, las técnicas de partición espacial no son inmunes a la maldición de la dimensionalidad y cuando el tamaño de la dimensionalidad aumenta más allá de un punto, es peor que una exploración lineal.
Distancia aproximada: 
Un enfoque complementario es hacer una exploración lineal con una medida de distancia aproximada. Esto se puede generalizar a la familia de hashing sensible a la localidad, un enfoque probabilístico para calcular vecinos aproximados. LSH también se puede usar como una técnica de partición, pero la tendencia está en usar el código hash LSH para aproximar la distancia, en lugar de un índice. Durante la fase de indexación, los vectores de la base de datos se reducen a códigos hash utilizando LSH y se almacenan como índice. Dado un punto de consulta, su código tiene se compara con todos los puntos de la base de datos en el espacio de código. Gracias al avance en los procesadores modernos, esta “comparación de código” es muy rápida (pocas instrucciones), en comparación con la distancia basada en vectores. Por lo tanto, se puede escalar incluso a millones de puntos. Algunas aproximaciones de distancia LSH comunes son
- Distancia Jaccard: MinHash
- Similitud de coseno: proyección aleatoria + cuantización basada en signos Técnicas de estimación de similitud de algoritmos de redondeo
- Distancia euclidiana: E2LSH Esquema de hash sensible a la localidad basado en distribuciones p-estables
Enfoque basado en el aprendizaje:
Esto también se conoce como Aprendizaje de funciones hash. Parte de los datos se usa para entrenar funciones hash, que se usarán para indexar los datos. Una vez más, la función hash aprendida también se puede usar para aproximar la distancia si la función hash está en el espacio hamming. Aprender códigos binarios de hash para la búsqueda de imágenes a gran escala y los códigos pequeños y las bases de datos de imágenes grandes para el reconocimiento brindan una buena visión general sobre el aprendizaje de funciones hash Algunos de los enfoques populares son:
- Hash semántico: este es uno de los primeros enfoques populares sobre el uso de la función hash supervisada y aprendida para transformar los datos en espacio de hamming. Entrenaron una red de creencias profundas para mapear vectores reales a códigos binarios.
- Hashing espectral: aplicaron técnicas espectrales en el gráfico de similitud para obtener códigos hash. Esta es una de las técnicas ampliamente comparadas.
- Cuantización del producto: Esta es una técnica de aprendizaje no supervisada, donde las dimensiones se agrupan y agrupan por separado utilizando K-Means. Se asigna un punto de datos para indexar a estos grupos de clúster por separado y los identificadores de clúster de estos grupos se concatenan para obtener un código compacto global.
