Optimal multi-step k-nearest neighbor search

ABSTRACT

For an increasing number of modern database applications, efficient support of similarity search becomes an important task. Along with the complexity of the objects such as images, molecules and mechanical parts, also the complexity of the similarity models increases more and more. Whereas algorithms that are directly based on indexes work well for simple medium-dimensional similarity distance functions, they do not meet the efficiency requirements of complex high-dimensional and adaptable distance functions. The use of a multi-step query processing strategy is recommended in these cases, and our investigations substantiate that the number of candidates which are produced in the filter step and exactly evaluated in the refinement step is a fundamental efficiency parameter. After revealing the strong performance shortcomings of the state-of-the-art algorithm for k-nearest neighbor search [Korn et al. 1996], we present a novel multi-step algorithm which is guaranteed to produce the minimum number of candidates. Experimental evaluations demonstrate the significant performance gain over the previous solution, and we observed average improvement factors of up to 120 for the number of candidates and up to 48 for the total runtime.

REFERENCES

• AFS 93: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• AKS 98: Ankerst M., Kriegel H.-P., Seidl T.: 'Pixel-based Shape Similarity Search in Large Image Databases', submitted for publication.
• ALSS 95: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• AMN 95: Sunil Arya , David M. Mount , Onuttom Narayan, Accounting for boundary effects in nearest neighbor searching, Proceedings of the eleventh annual symposium on Computational geometry, p.336-344, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220315]
• BBKK 97: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• Ber+97: Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.1-12, May 11-15, 1997, Tucson, Arizona, United States
• Ber+98: Stefan Berchtold , Bernhard Ertl , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Fast Nearest Neighbor Search in High-Dimensional Space, Proceedings of the Fourteenth International Conference on Data Engineering, p.209-218, February 23-27, 1998
• BHKS 93: Thomas Brinkhoff , Holger Horn , Hans-Peter Kriegel , Ralf Schneider, A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.357-376, June 23-25, 1993
• BKK 96: 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
• BK 97: Stefan Berchtold , Hans-Peter Kriegel, S3: similarity search in CAD database systems, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.564-567, May 11-15, 1997, Tucson, Arizona, United States
• BMH 92: Anne Badel , Jean Paul Mornon , Serge Hazout, Searching for geometric molecular shape complementarity using bidimensional surface profiles, Journal of Molecular Graphics, v.10 n.4, p.205-211, Dec. 1992 [doi>10.1016/0263-7855(92)80069-P]
• CPZ 97: 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
• Fal+ 94: 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]
• FBF 77: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• FL 95: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• FRM 94: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• GG 97: 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]
• GM 93: James E. Gary , Rajiv Mehrotra, Similar shape retrieval using a structural feature index, Information Systems, v.18 n.7, p.525-537, Oct. 1993 [doi>10.1016/0306-4379(93)90005-L]
• Haf+95: James Hafner , Harpreet S. Sawhney , Will Equitz , Myron Flickner , Wayne Niblack, Efficient Color Histogram Indexing for Quadratic Form Distance Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.7, p.729-736, July 1995 [doi>10.1109/34.391417]
• Hen 94: Henrich, A.: 'A Distance-Scan Algorithm for Spatial Access Structures', Proc. 2nd ACM Workshop on Advances in Geographic Information Systems, Gaithersburg, Maryland, 1994, pp. 136-143.
• HS 95: 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
• Jag 91: H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States
• Kor+96: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• KS 98: Hans-Peter Kriegel , Thomas Seidl, Approximation-Based Similarity Search for 3-D Surface Segments, Geoinformatica, v.2 n.2, p.113-147, June 1998 [doi>10.1023/A:1009760031965]
• KSS 97: Hans-Peter Kriegel , Thomas Schmidt , Thomas Seidl, 3D Similarity Search by Shape Approximation, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.11-28, July 15-18, 1997
• OM 88: J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988 [doi>10.1109/32.6139]
• PM 97: Apostolos Papadopoulos , Yannis Manolopoulos, Performance of Nearest Neighbor Queries in R-Trees, Proceedings of the 6th International Conference on Database Theory, p.394-408, January 08-10, 1997
• PS 93: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• RKV 95: 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
• RP 92: Ramasubramanian V., Paliwal K. K.: 'Fast k-Dimensional Tree Algorithms for Nearest Neighbor Search with Application to Vector Quantization Encoding', IEEE Transactions on Signal Processing, Vol. 40, No. 3, March 1992, pp. 518-531.
• Sei 97: Seidl T.: 'Adaptable Similarity Search in 3-D Spatial Database Systems', PhD thesis, Institute for Computer Science, University of Munich, 1997.
• SK 97: Thomas Seidl , Hans-Peter Kriegel, Efficient User-Adaptable Similarity Search in Large Multimedia Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.506-515, August 25-29, 1997
• Spr 91: Sproull R.F.: "Refinements to Nearest Neighbor Searching in k-Dimensional Trees', Algorithmica 1991, pp. 579-589.
• WJ 96: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Measurement, Verification