La búsqueda por similitud es el término más general usado para una variedad de mecanismos que comparten el principio de buscar espacios de objetos (típicamente, muy grandes) donde el único comparador disponible es la similitud entre cualquier par de objetos. Esto es cada vez más importante 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 de vecino más cercano y las consultas de rango son subclases importantes de búsqueda de similitud, y existen varias soluciones. La investigación en Búsqueda de similitudes está dominada por los problemas inherentes a la búsqueda de objetos complejos. Tales objetos hacen que la mayoría de las técnicas conocidas pierdan tracción sobre grandes colecciones, debido a una manifestación de la llamada Maldición de la dimensionalidad , y todavía quedan muchos problemas sin resolver. Desafortunadamente, en muchos casos en los que es necesaria la búsqueda de similitudes, los objetos son intrínsecamente complejos.
El enfoque más general para la búsqueda de similitudes se basa en la noción matemática de espacio métrico , que permite la construcción de estructuras de índices eficientes para lograr escalabilidad en el dominio de búsqueda.
La búsqueda de similitudes evolucionó de forma independiente en varios contextos científicos e informáticos diferentes, de acuerdo con diversas necesidades. En 2008, algunos investigadores destacados en el campo sintieron firmemente que el tema debería ser un tema de investigación por derecho propio, para permitir centrarse en los problemas generales aplicables en los diversos dominios de su uso. Esto resultó en la formación de la fundación SISAP , cuya actividad principal es una serie de conferencias internacionales anuales sobre el tema genérico.
Búsqueda métrica
La búsqueda métrica es una búsqueda de similitudes que tiene lugar dentro de espacios métricos . Si bien las propiedades semimétricas son más o menos necesarias para que cualquier tipo de búsqueda sea significativa, la propiedad adicional de la desigualdad de triángulos es útil para fines de ingeniería, más que conceptuales.
Un corolario simple de la desigualdad de triángulos es que, si dos objetos cualesquiera dentro del espacio están muy separados, 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 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 según la distancia a este objeto: los que están cerca del objeto de referencia en el conjunto A y los que están lejos del objeto en el conjunto. conjunto B . Si, cuando se consulta posteriormente el conjunto, la distancia desde la consulta al 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ño, ningún objeto dentro del conjunto B puede estar cerca de la consulta.
Una vez que estas situaciones se cuantifican y estudian, se pueden diseñar muchas estructuras de indexación métrica diferentes, de diversas formas adecuadas para diferentes tipos de colecciones. Por tanto, el dominio de investigación de la búsqueda métrica puede caracterizarse 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 similitudes eficiente.
Otros tipos de búsqueda de similitudes
Hash sensible a la localidad
Un enfoque popular para la búsqueda de similitudes es el hash sensible a la localidad (LSH). [1] aplica hash a los elementos de entrada para que los elementos similares se asignen a los mismos "depósitos" en la memoria con alta probabilidad (el número de depósitos es mucho menor que el universo de posibles elementos de entrada). A menudo se aplica en la búsqueda de vecinos más cercanos 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 de tiempo y bases de datos de genomas. [2]
Benchmarks
http://ann-benchmarks.com/ - ANN-Benchmarks es un entorno de evaluación comparativa para la búsqueda aproximada de algoritmos de vecinos más cercanos, fue creado por el equipo de recomendación de Spotify
Ver también
Ciclo de fundaciones y conferencias SISAP : www.sisap.org
Bibliografía
- Pei Lee, Laks VS Lakshmanan, Jeffrey Xu Yu: Búsqueda de similitudes estructurales en Top-k. ICDE 2012: 774-785
- Zezula, P., Amato, G., Dohnal, V. y Batko, M. Búsqueda de similitudes: el enfoque del espacio métrico. Springer, 2006. ISBN 0-387-29146-6
- Samet, H .. Fundamentos de estructuras de datos métricas y multidimensionales. Morgan Kaufmann, 2006. ISBN 0-12-369446-9
- E. Chavez, G. Navarro, RA Baeza-Yates, JL Marroquin, Buscando en espacios métricos , Encuestas de Computación ACM, 2001
- ML Hetland, The Basic Principles of Metric Indexing , Swarm Intelligence for Multi-Object Problems in Data Mining, Studies in Computational Intelligence Volume 242, 2009, pp 199-232
Recursos
Referencias
- ^ Gionis, Arístides, Piotr Indyk y Rajeev Motwani. "Búsqueda de similitudes en grandes dimensiones mediante hash". VLDB. Vol. 99. No. 6. 1999.
- ^ Rajaraman, A .; Ullman, J. (2010). "Minería de conjuntos de datos masivos, cap. 3" .