New techniques for best-match retrieval
作者： Dennis Shasha , Tsong-Li Wang
DOI: 10.1145/96105.96111
关键词:
摘要: A scheme to answer best-match queries from a file containing collection of objects is described. query find the in that are closest (according some (dis)similarity measure) given target.Previous work [5, 331] suggests one can reduce number comparisons required achieve desired results using triangle inequality, starting with data structure for reflects precomputed intrafile distances. We generalize technique allow optimum use any set Some empirical presented which illustrate effectiveness our scheme, and its performance relative previous algorithms.
acm.org
core.ac.uk
sci-hub.se 参考文章(38)
Clyde P. Kruskal, Richard C. Paige, Parallel Algorithms for Shortest Path Problems. international conference on parallel processing. pp. 14- 20 ,(1985)
Dennis Shasha, Jason Tsong-Li Wang, Query Processing for Distance Metrics very large data bases. pp. 602- 613 ,(1990)
H. V. Jagadish, Rakesh Agrawal, Efficient Search in Very Large Databases very large data bases. pp. 407- 418 ,(1988)
Gerard Salton, Michael J. McGill, Introduction to Modern Information Retrieval ,(1983)
Caroline M. Eastman, Stephen F. Weiss, A tree algorithm for nearest neighbor searching in document retrieval systems ACM SIGIR Forum. ,vol. 13, pp. 131- 149 ,(1978) , 10.1145/1013234.803139
F. Murtagh, Expected-time complexity results for hierarchic clustering algorithms which use cluster centres Information Processing Letters. ,vol. 16, pp. 237- 241 ,(1983) , 10.1016/0020-0190(83)90095-9
Christine Pogue, Peter Willett, An evaluation of document retrieval from serial files using the ICL Distributed Array Processor Online Information Review. ,vol. 8, pp. 569- 584 ,(1984) , 10.1108/EB024172
C.M. Eastman, M. Zemankova, Partially specified nearest neighbor searches using k-d trees☆ Information Processing Letters. ,vol. 15, pp. 53- 56 ,(1982) , 10.1016/0020-0190(82)90106-5
Marvin Shapiro, The choice of reference points in best-match file searching Communications of the ACM. ,vol. 20, pp. 339- 343 ,(1977) , 10.1145/359581.359599
W. A. Burkhard, R. M. Keller, Some approaches to best-match file searching Communications of the ACM. ,vol. 16, pp. 230- 236 ,(1973) , 10.1145/362003.362025