Spatial selection of sparse pivots for similarity search in metric spaces

• Autores: Nieves R. Brisaboa , Antonio Fariña , Oscar Pedreira , Nora Susana Reyes
• Localización: Journal of Computer Science and Technology, ISSN-e 1666-6038, Vol. 7, Nº. 1, 2007 (Ejemplar dedicado a: Nineteenth Issue), págs. 8-13
• Idioma: inglés
• Enlaces
  • Texto completo
• Dialnet Métricas: 1 Cita
• Resumen

  • Similarity search is a fundamental operation for applications that deal with unstructured data sources. In this paper we propose a new pivot-based method for similarity search, called Sparse Spatial Selection (SSS). The main characteristic of this method is that it guarantees a good pivot selection more efficiently than other methods previously proposed. In addition, SSS adapts itself to the dimensionality of the metric space we are working with, without being necessary to specify in advance the number of pivots to use. Furthermore, SSS is dynamic, that is, it is capable to support object insertions in the database efficiently, it can work with both continuous and discrete distance functions, and it is suitable for secondary memory storage. In this work we provide experimental results that confirm the advantages of the method with several vector and metric spaces. We also show that the efficiency of our proposal is similar to that of other existing ones over vector spaces, although it is better over general metric spaces.

• Referencias bibliográficas
  • References [1] Ricardo Baeza-Yates. Searching: an algorithmic tour. Encyclopedia of Computer Science and Technology, 37:331-359, 1997.
  • [2] Ricardo Baeza-Yates, Walter Cunto, Udi Manber, and Sun Wu. Proximity matching using fixed-queries trees. In Proceedings of the 5th Annual...
  • [3] Tolga Bozkaya and Meral Ozsoyoglu. Distance-based indexing for high-dimensional metric spaces. In Proceedings of the ACM International...
  • [4] Sergey Brin. Near neighbor search in large metric spaces. In 21st conference on Very Large Databases (VLDB), 1995.
  • [5] Walter A. Burkhard and Robert M. Keller. Some approaches to best-match file searching. Communications of the ACM, 16(4):230-236, April...
  • [6] Benjamín Bustos, Gonzalo Navarro, and Edgar Chávez. Pivot selection techniques for proximity search in metric spaces. In SCCC 2001, Proceedings...
  • [7] Edgar Chávez, José Luis Marroquín, and Gonzalo Navarro. Overcoming the curse of dimensionality. In European Workshop on Content-based...
  • [8] Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José Luis Marroquín. Searching in metric spaces. ACM Computing Surveys, 33(3):273-321,...
  • [9] Iraj Kalantari and Gerard McDonald. A data structure and an algorithm for the nearest point problem. IEEE Transactions on Software Engineering,...
  • [10] Luisa Micó, José Oncina, and R. Enrique Vidal. A new version of the nearest-neighbor approximating and eliminating search (AESA) with...
  • [11] Gonzalo Navarro. Searching in metric spaces by spatial approximation. In Proceedings of String Processing and Information Retrieval (SPIRE'99),...
  • [12] Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40:175-179, 1991.
  • [13] Enrique Vidal. An algorithm for finding nearest neighbors in (aproximately) constant average time. Pattern Recognition Letters, 4:145-157,...
  • [14] Peter Yianilos. Data structures and algorithms for nearest-neighbor search in general metric spaces. In Proceedings of the fourth annual...
  • [15] Peter Yianilos. Excluded middle vantage point forests for nearest neighbor search. In Proceedings of the 6th DIMACS Implementation Challenge:...
  • [16] Pavel Zezula, Giuseppe Amato, Vlatislav Dohnal, and Michal Batko. Similarity search. The metric space approach, volume 32 of Advances...