Searching in metric spaces

ABSTRACT

The problem of searching the elements of a set that are close to a given query element under some similarity criterion has a vast number of applications in many branches of computer science, from pattern recognition to textual and multimedia information retrieval. We are interested in the rather general case where the similarity criterion defines a metric space, instead of the more restricted case of a vector space. Many solutions have been proposed in different areas, in many cases without cross-knowledge. Because of this, the same ideas have been reconceived several times, and very different presentations have been given for the same approaches. We present some basic results that explain the intrinsic difficulty of the search problem. This includes a quantitative definition of the elusive concept of "intrinsic dimensionality." We also present a unified view of all the known proposals to organize metric spaces, so as to be able to understand them under a common framework. Most approaches turn out to be variations on a few different concepts. We organize those works in a taxonomy that allows us to devise new algorithms from combinations of concepts not noticed before because of the lack of communication between different communities. We present experiments validating our results and comparing the existing approaches. We finish with recommendations for practitioners and open questions for future development.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. M.G. Apers , H. M. Blanken , M. A. Houtsma, Multimedia Databases in Perspective, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	2	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	3	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	4	BAEZA-YATES, R. 1997. Searching: An algorithmic tour. In Encyclopedia of Computer Science and Technology, vol. 37, A. Kent and J. Williams, Eds., Marcel Dekker, New York, 331-359.
	5	BAEZA-YATES,R.AND NAVARRO, G. 1998. Fast approximate string matching in a dictionary. In Proceedings of the Fifth South American Symposium on String Processing and Information Retrieval (SPIRE'98), IEEE Computer Science Press, Los Alamitos, Calif., 14-22.
	6	Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
	7	Ricardo A. Baeza-Yates , Walter Cunto , Udi Manber , Sun Wu, Proximity Matching Using Fixed-Queries Trees, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.198-212, June 05-08, 1994
	8	Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
	9	BENTLEY, J. 1979. Multidimensional binary search trees in database applications. IEEE Trans. Softw. Eng. 5, 4, 333-340.
	10	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
	11	Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
	12	B. Bhanu , J. Peng , S. Qing, Learning Feature Relevance and Similarity Metrics in Image Databases, Proceedings of the IEEE Workshop on Content - Based Access of Image and Video Libraries, p.14, June 21-21, 1998
	13	A. Del Bimbo , E. Vicario, Using Weighted Spatial Relationships in Retrieval by Visual Contents, Proceedings of the IEEE Workshop on Content - Based Access of Image and Video Libraries, p.35, June 21-21, 1998
	14	Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
	15	Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
	16	Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
	17	BRITO, M., CH~VEZ, E., QUIROZ, A., AND YUKICH,J. 1996. Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection. Stat. Probab. Lett. 35, 33-42.
	18	BUGNION, E., FHEI, S., ROOS, T., WIDMAYER,P., AND WIDMER, F. 1993. A spatial index for approximate multiple string matching. In Proceedings of the First South American Workshop on String Processing (WSP'93), R. Baeza-Yates and N. Ziviani, Eds., 43-53.
	19	W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
	20	M. La Cascia , S. Sethi , S. Sclaroff, Combining Textual and Visual Cues for Content-Based Image Retrieval on the World Wide Web, Proceedings of the IEEE Workshop on Content - Based Access of Image and Video Libraries, p.24, June 21-21, 1998
	21	CH~VEZ, E. 1999. Optimal discretization for pivot based algorithms. Manuscript. ftp:// garota.fismat.umich.mx/pub/users/elchavez/ minimax.ps.gz.
	22	CH~VEZ,E.AND MARROQUYN, J. 1997. Proximity queries in metric spaces. In Proceedings of the Fourth South American Workshop on String Processing ( WSP'97), R. Baeza-Yates, Ed. Carleton University Press, Ottawa, 21-36.
	23	E. Chavez , G. Navarro, An Effective Clustering Algorithm to Index High Dimensional Metric Spaces, Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), p.75, September 27-29, 2000
	24	CH~VEZ,E.AND NAVARRO, G. 2001a. Towards measuring the searching complexity of metric spaces. In Proceedings of the Mexican Computing Meeting, vol. II, 969-972.
	25	Edgar Chávez , Gonzalo Navarro, A Probabilistic Spell for the Curse of Dimensionality, Revised Papers from the Third International Workshop on Algorithm Engineering and Experimentation, p.147-160, January 05-06, 2001
	26	Edgar Chávez , Gonzalo Navarro, A Metric Index for Approximate String Matching, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.181-195, April 03-06, 2002
	27	Edgar Chávez , J. L. Marroquín , Ricardo Baeza-Yates, Spaghettis: An Array Based Algorithm for Similarity Queries in Metric Spaces, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.38, September 21-24, 1999
	28	Edgar Chávez , José L. Marroquín , Gonzalo Navarro, Fixed Queries Array: A Fast and Economical Data Structure for Proximity Searching, Multimedia Tools and Applications, v.14 n.2, p.113-135, June 2001 [doi>10.1023/A:1011343115154]
	29	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195110]
	30	Tzi-cker Chiueh, Content-Based Image Indexing, Proceedings of the 20th International Conference on Very Large Data Bases, p.582-593, September 12-15, 1994
	31	Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
	32	Paolo Ciaccia , Marco Patella , Pavel Zezula, A cost model for similarity queries in metric spaces, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-68, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275495]
	33	Paolo Ciaccia , Marco Patella , Pavel Zezula, Processing Complex Similarity Queries with Distance-Based Access Methods, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.9-23, March 23-27, 1998
	34	CLARKSON, K. 1999. Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22,1, 63-93.
	35	COX,T.AND COX, M. 1994. Multidimensional Scaling. Chapman and Hall, London.
	36	F. Dehne , H. Noltemeier, Vorono trees and clustering problems, Information Systems, v.12 n.2, p.171-175, June 1987 [doi>10.1016/0306-4379(87)90041-X]
	37	Luc Devroye, A course in density estimation, Birkhauser Boston Inc., Cambridge, MA, 1987
	38	DUDA,R.AND HART, P. 1973. Pattern Classification and Scene Analysis. Wiley, New York.
	39	Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
	40	Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, ACM SIGMOD Record, v.24 n.2, p.163-174, May 1995
	41	C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
	42	A. Faragó , T. Linder , G. Lugosi, Fast Nearest-Neighbor Search in Dissimilarity Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.957-962, September 1993 [doi>10.1109/34.232083]
	43	William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	44	Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
	45	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	46	Joseph F. Hair, Jr. , Rolph E. Anderson , Ronald L. Tatham , William C. Black, Multivariate data analysis (4th ed.): with readings, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	47	Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
	48	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	49	KALANTARI,I.AND MCDONALD, G. 1983. A data structure and an algorithm for the nearest point problem. IEEE Trans. Softw. Eng. 9,5.
	50	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	51	Luisa Micó , Jose Oncina , Rafael C. Carrasco, A fast branch & bound nearest neighbour classifier in metric spaces, Pattern Recognition Letters, v.17 n.7, p.731-739, June 10, 1996 [doi>10.1016/0167-8655(96)00032-3]
	52	María Luisa Micó , José Oncina , Enrique Vidal, A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements, Pattern Recognition Letters, v.15 n.1, p.9-17, Jan. 1994 [doi>10.1016/0167-8655(94)90095-7]
	53	Gonzalo Navarro, Searching in Metric Spaces by Spatial Approximation, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.141, September 21-24, 1999
	54	NAVARRO,G.AND REYES, N. 2001. Dynamic spatial approximation trees. In Proceedings of the Eleventh Conference of the Chilean Computer Science Society (SCCC'01), IEEE CS Press, 213-222.
	55	Sameer A. Nene , Shree K. Nayar, A Simple Algorithm for Nearest Neighbor Search in High Dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.9, p.989-1003, September 1997 [doi>10.1109/34.615448]
	56	J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
	57	NOLTEMEIER, H. 1989. Voronoi trees and applications. In Proceedings of the International Workshop on Discrete Algorithms and Complex-ity (Fukuoka, Japan), 69-74.
	58	Hartmut Noltemeier , Knut Verbarg , Christian Zirkelbach, Monotonous Bisector* Trees - A Tool for Efficient Partitioning of Complex Scenes of Geometric Objects, Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, p.186-203, January 1992
	59	Sunil Prabhakar , Divyakant Agrawal , Amr El Abbadi, Efficient disk allocation for fast similarity searching, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.78-87, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277674]
	60	Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
	61	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	62	Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
	63	SANKOFF,D.AND KRUSKAL, J., EDS. 1983. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, Mass.
	64	Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990 [doi>10.1145/96105.96111]
	65	Marvin Shapiro, The choice of reference points in best-match file searching, Communications of the ACM, v.20 n.5, p.339-343, May 1977 [doi>10.1145/359581.359599]
	66	Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
	67	UHLMANN, J. 1991a. Implementing metric trees to satisfy general proximity/similarity queries. Manuscript.
	68	UHLMANN, J. 1991b. Satisfying general proximity/ similarity queries with metric trees. Inf. Proc. Lett. 40, 175-179.
	69	VERBARG, K. 1995. The C-Ttree: A dynamically balanced spatial index. Comput. Suppl. 10, 323-340.
	70	E V Ruiz, An algorithm for finding nearest neighbours in (approximately) constant average time, Pattern Recognition Letters, v.4 n.3, p.145-157, July 1986 [doi>10.1016/0167-8655(86)90013-9]
	71	WATERMAN, M. 1995. Introduction to Computational Biology. Chapman and Hall, London.
	72	Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
	73	WHITE,D.AND JAIN, R. 1996. Algorithms and strategies for similarity retrieval. Tech. Rep. VCL-96-101 (July), Visual Computing Laboratory, University of California, La Jolla.
	74	YAO, A. 1990. Computational Geometry,J.Van Leeuwen, Ed. Elsevier Science, New York, 345-380.
	75	Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
	76	YIANILOS, P. 1999. Excluded middle vantage point forests for nearest neighbor search. In DIMACS Implementation Challenge, ALENEX'99 (Baltimore, Md).
	77	Peter N. Yianilos, Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.361-370, January 09-11, 2000, San Francisco, California, United States
	78	Atsuo Yoshitaka , Tadao Ichikawa, A Survey on Content-Based Retrieval for Multimedia Databases, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.81-93, January 1999 [doi>10.1109/69.755617]