La búsqueda por similitud es el término más general que se utiliza para una serie de mecanismos que comparten el principio de búsqueda en espacios (normalmente muy grandes) de objetos donde el único comparador disponible es la similitud entre cualquier par de objetos. Esto cobra cada vez mayor importancia en una era de grandes depósitos de información donde los objetos contenidos no poseen ningún orden natural, por ejemplo, grandes colecciones de imágenes, sonidos y otros objetos digitales sofisticados.
La búsqueda del vecino más cercano y las consultas de rango son subclases importantes de la búsqueda de similitud, y existe una serie de soluciones. La investigación en búsqueda de similitud está dominada por los problemas inherentes a la búsqueda en objetos complejos. Dichos objetos hacen que la mayoría de las técnicas conocidas pierdan fuerza en colecciones grandes, debido a una manifestación de la llamada maldición de la dimensionalidad , y aún quedan muchos problemas sin resolver. Desafortunadamente, en muchos casos en los que es necesaria la búsqueda de similitud, los objetos son inherentemente complejos.
El enfoque más general para la búsqueda de similitud se basa en la noción matemática de espacio métrico , que permite la construcción de estructuras de índice eficientes para lograr escalabilidad en el dominio de búsqueda.
La búsqueda de similitudes evolucionó de manera independiente en diversos contextos científicos e informáticos, según las distintas necesidades. En 2008, algunos investigadores destacados en el campo consideraron firmemente que el tema debía ser un tema de investigación por derecho propio, para poder centrarse en las cuestiones generales aplicables a los diversos dominios de su uso. Esto dio lugar a la formación de la fundación SISAP, cuya actividad principal es una serie de conferencias internacionales anuales sobre el tema genérico.
La búsqueda métrica es una búsqueda de similitud que se lleva a cabo dentro de espacios métricos . Si bien las propiedades semimétricas son más o menos necesarias para que cualquier tipo de búsqueda tenga sentido, la propiedad adicional de la desigualdad triangular es útil para fines de ingeniería, más que conceptuales.
Un corolario simple de la desigualdad triangular es que, si dos objetos dentro del espacio están muy separados, entonces ningún tercer objeto puede estar cerca de ambos. Esta observación permite construir estructuras de datos, basadas en distancias medidas dentro de la colección de datos, que permiten excluir subconjuntos de los datos cuando se ejecuta una consulta. Como ejemplo simple, se puede elegir un objeto de referencia del conjunto de datos, y el resto del conjunto se puede dividir en dos partes en función de la distancia a este objeto: aquellas cercanas al objeto de referencia en el conjunto A y aquellas alejadas del objeto en el conjunto B. Si, cuando el conjunto se consulta más tarde, la distancia desde la consulta hasta el objeto de referencia es grande, entonces ninguno de los objetos dentro del conjunto A puede estar muy cerca de la consulta; si es muy pequeña, entonces ningún objeto dentro del conjunto B puede estar cerca de la consulta.
Una vez cuantificadas y estudiadas estas situaciones, se pueden diseñar muchas estructuras de indexación métrica diferentes, adecuadas para distintos tipos de colecciones. El campo de investigación de la búsqueda métrica puede caracterizarse, por tanto, como el estudio de algoritmos de preprocesamiento sobre colecciones de datos grandes y relativamente estáticas que, utilizando las propiedades de los espacios métricos, permiten realizar una búsqueda de similitud eficiente.
Un método popular para la búsqueda de similitudes es el hash sensible a la localidad (LSH, por sus siglas en inglés). [1] Este método realiza un hash de los elementos de entrada de modo que los elementos similares se asignen a los mismos "cubos" en la memoria con una alta probabilidad (la cantidad de cubos es mucho menor que el universo de posibles elementos de entrada). A menudo se aplica en la búsqueda del vecino más cercano en datos de alta dimensión a gran escala, por ejemplo, bases de datos de imágenes, colecciones de documentos, bases de datos de series temporales y bases de datos de genomas. [2]
Fundación SISAP y ciclo de conferencias: www.sisap.org