Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Center selection techniques for metric indexes
Keywords:
Databases, Metric Spaces, Similarity Search, Index, Centers SelectionAbstract
The metric spaces model formalizes the similarity search concept in nontraditional databases. The goal is to build an index designed to save distance computations when answering similarity queries later. A large class of algorithms to build the index are based on partitioning the space in zones as compact as possible. Each zone stores a representative point, called center, and a few extra data that allow to discard the entire zone at query time without measuring the actual distance between the elements of the zone and the query object. The way in which the centers are selected affects the performance of the algorithm. In this paper, we introduce two new center selection techniques for compact partition based indexes. These techniques were evaluated using the Geometric Near-neighbor Access Tree (GNAT). We experimentally showed that they achieve good performance.
Downloads
Download data is not yet available.
References
[1] R. Baeza-Yates, B. Bustos, E. Chávez, N. Herrera, and G. Navarro. Clustering in Metric Spaces and Its Application to Information Retrieval. Kluwer Academic Publishers, 2003. ISBN 1-4020-7682-7.
[2] R. Baeza-Yates, W. Cunto, U. Manber, and S.Wu. Proximity matching using fixed-queries trees. In Proc. 5th Combinatorial Pattern Matching (CPM’94), LNCS 807, pages 198–212, 1994.
[3] S. Brin. Near neighbor search in large metric spaces. In Proc. 21st Conference on Very Large Databases (VLDB’95), pages 574–584, 1995.
[4] E. Chavez and K. Figueroa. Faster proximity searching in metric data. In Proceedings of MICAI 2004. LNCS 2972, Springer, Cd. de México, México, 2004.
[5] E. Chavez, J. Marroquin, and G. Navarro.Fixed queries array: A fast and economical data structure for proximity searching. Multimedia Tools and Applications(MTAP), 14(2):113–135, 2001.
[6] E.Chavez, G. Navarro, R.Baeza-Yates, and J.L. Marroquin. Searching in metric spaces. ACM Computing Surveys, 33(3):273–321, September 2001.
[7] G. Navarro. Searching in metric spaces by spatial approximation. In Proc. String Processing and Information Retrieval (SPIRE’99), pages 141–148. IEEE CS Press, 1999.
[8] J. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40:175–179,1991.
[2] R. Baeza-Yates, W. Cunto, U. Manber, and S.Wu. Proximity matching using fixed-queries trees. In Proc. 5th Combinatorial Pattern Matching (CPM’94), LNCS 807, pages 198–212, 1994.
[3] S. Brin. Near neighbor search in large metric spaces. In Proc. 21st Conference on Very Large Databases (VLDB’95), pages 574–584, 1995.
[4] E. Chavez and K. Figueroa. Faster proximity searching in metric data. In Proceedings of MICAI 2004. LNCS 2972, Springer, Cd. de México, México, 2004.
[5] E. Chavez, J. Marroquin, and G. Navarro.Fixed queries array: A fast and economical data structure for proximity searching. Multimedia Tools and Applications(MTAP), 14(2):113–135, 2001.
[6] E.Chavez, G. Navarro, R.Baeza-Yates, and J.L. Marroquin. Searching in metric spaces. ACM Computing Surveys, 33(3):273–321, September 2001.
[7] G. Navarro. Searching in metric spaces by spatial approximation. In Proc. String Processing and Information Retrieval (SPIRE’99), pages 141–148. IEEE CS Press, 1999.
[8] J. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40:175–179,1991.
Downloads
Published
2007-03-01
Issue
Section
Original Articles
License
How to Cite
[1]
“Center selection techniques for metric indexes”, JCS&T, vol. 7, no. 01, pp. p. 98–104, Mar. 2007, Accessed: Jan. 17, 2026. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/810
