ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Some approaches to best-match file searching
Full text PdfPdf (709 KB)
Source
Communications of the ACM archive
Volume 16 ,  Issue 4  (April 1973) table of contents
Pages: 230 - 236  
Year of Publication: 1973
ISSN:0001-0782
Authors
W. A. Burkhard  Univ. of California, San Diego
R. M. Keller  Princeton Univ., Princeton, NJ
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 14,   Downloads (12 Months): 121,   Citation Count: 47
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/362003.362025
What is a DOI?

ABSTRACT

The problem of searching the set of keys in a file to find a key which is closest to a given query key is discussed. After “closest,” in terms of a metric on the the key space, is suitably defined, three file structures are presented together with their corresponding search algorithms, which are intended to reduce the number of comparisons required to achieve the desired result. These methods are derived using certain inequalities satisfied by metrics and by graph-theoretic concepts. Some empirical results are presented which compare the efficiency of the methods.


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
Chang, H.Y., and Thomas, W. Methods of interpreting diagnostic data for locating faults in digital machines. Bell Syst. Tech. J. (1967), 289-317.
 
2
Wipke, W.T. Private communication. Dep. of Chem., Princeton U., Princeton, N.J.
 
3
Perceptrons: An Introduction to Computational Geometry, The MIT Press, 1969
4
Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968  [doi>10.1145/362851.362882]
 
5
Jackson, D.M. Classification, relevance, and information retrieval. Advances in Computers Vol. 11, Academic Press, N.Y., 1971.
 
6
Litofsky, B., and Prywes, N.S. All-automatic processing for a large library. Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., pp. 323-331.
 
7
Salton, G. Experiments in automatic thesaurus construction for information retrieval. Proc. IFIP Congress 1971, North Holland Pub. Co., Amsterdam.
8
J. Gary Augustson , Jack Minker, An Analysis of Some Graph Theoretical Cluster Techniques, Journal of the ACM (JACM), v.17 n.4, p.571-588, Oct. 1970  [doi>10.1145/321607.321608]
9
Gordon D. Mulligan , D. G. Corneil, Corrections to Bierstone's Algorithm for Generating Cliques, Journal of the ACM (JACM), v.19 n.2, p.244-247, April 1972  [doi>10.1145/321694.321698]
 
10
Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
 
11
Bron, C., and Kerbosh, J.A.G.M. Finding all cliques of an undirected graph. (To be published.)

CITED BY  47
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
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
Tetsuro Ito , Makoto Kizawa, Hierarchical file organization and its application to similar-string matching, ACM Transactions on Database Systems (TODS), v.8 n.3, p.410-433, Sept. 1983
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
Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States
John Gerald Cleary, Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.183-192, June 1979
Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001
Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, ACM SIGMOD Record, v.26 n.2, p.357-368, June 1997
Caroline M. Eastman , Stephen F. Weiss, A tree algorithm for nearest neighbor searching in document retrieval systems, ACM SIGIR Forum, v.13 n.1, p.131-149, May 1978
Tolga Bozkaya , Meral Ozsoyoglu, Indexing large metric spaces for similarity search queries, ACM Transactions on Database Systems (TODS), v.24 n.3, p.361-404, Sept. 1999
Dalia Motzkin, The use of normal multiplication tables for information storage and retrieval, Communications of the ACM, v.22 n.3, p.193-207, March 1979
Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999
C. J. van Rijsbergen, The best-match problem in document retrieval, Communications of the ACM, v.17 n.11, p.648-649, Nov. 1974
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
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
Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Caetano Traina, Jr. , Agma Traina , Roberto Santos Filho , Christos Faloutsos, How to improve the pruning ability of dynamic metric access methods, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
C. T. Yu , W. S. Luk, Analysis of Effectiveness of Retrieval in Clustered Files, Journal of the ACM (JACM), v.24 n.4, p.607-622, Oct. 1977
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
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
Alfredo Ferro , Giovanni Gallo , Rosalba Giugno , Alfredo Pulvirenti, Best-Match Retrieval for Structured Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.7, p.707-718, July 2001
Benjamin Bustos , Gonzalo Navarro , Edgar Chávez, Pivot selection techniques for proximity searching in metric spaces, Pattern Recognition Letters, v.24 n.14, p.2357-2366, October 2003
Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003
Alistair Morrison , Matthew Chalmers, A pivot-based routine for improved parent-finding in hybrid MDS, Information Visualization, v.3 n.2, p.109-122, June 2004
C. Traina, Jr. , A. Traina , C. Faloutsos , B. Seeger, Fast Indexing and Visualization of Metric Data Sets using Slim-Trees, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.244-260, March 2002
Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
Edgar Chávez , Gonzalo Navarro, A compact space decomposition for effective metric indexing, Pattern Recognition Letters, v.26 n.9, p.1363-1376, 1 July 2005
Renato Bueno , Agma J. M. Traina , Caetano Traina, Accelerating approximate similarity queries using genetic algorithms, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Kimmo Fredriksson, Exploiting distance coherence to speed up range queries in metric indexes, Information Processing Letters, v.95 n.1, p.287-292, 16 July 2005
Caetano Traina, Jr. , Roberto F. Filho , Agma J. Traina , Marcos R. Vieira , Christos Faloutsos, The Omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.483-505, October 2007
Kimmo Fredriksson, Engineering efficient metric indexes, Pattern Recognition Letters, v.28 n.1, p.75-84, January, 2007
Alexander Ocsa , Ernesto Cuadros-Vargas, DBM*-Tree: an efficient metric access method, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina
James Gorman , James R. Curran, Scaling distributional similarity to large corpora, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.361-368, July 17-18, 2006, Sydney, Australia
Walter A. Burkhard, Partial-match queries and file designs, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts
Michael L. Case , Victor N. Kravets , Alan Mishchenko , Robert K. Brayton, Merging nodes under sequential observability, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
Renato Bueno , Agma J. M. Traina , Caetano Traina, Jr., Genetic algorithms for approximate similarity queries, Data & Knowledge Engineering, v.62 n.3, p.459-482, September, 2007
Dragomir Yankov , Eamonn Keogh , Jose Medina , Bill Chiu , Victor Zordan, Detecting time series motifs under uniform scaling, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
Ada Wai-chee Fu , Polly Mei-shuen Chan , Yin-Ling Cheung , Yiu Sang Moon, Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.2, p.154-173, July 2000
Gonzalo Navarro, Searching in metric spaces by spatial approximation, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.1, p.28-46, August 2002
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
Jason Tsong-Li Wang , Dennis Shasha, Query Processing for Distance Metrics, Proceedings of the 16th International Conference on Very Large Data Bases, p.602-613, August 13-16, 1990
Veronica Gil-Costa , Mauricio Marin , Nora Reyes, Parallel query processing on distributed clustering indexes, Journal of Discrete Algorithms, v.7 n.1, p.3-17, March, 2009
Lior Aronovich , Israel Spiegler, CM-tree: A dynamic clustered index for similarity search in metric databases, Data & Knowledge Engineering, v.63 n.3, p.919-946, December, 2007
Gonzalo Navarro , Rodrigo Paredes , Edgar Chávez, t-Spanners for metric space searching, Data & Knowledge Engineering, v.63 n.3, p.820-854, December, 2007
Jayendra Venkateswaran , Tamer Kahveci , Christopher Jermaine , Deepak Lachwani, Reference-based indexing for metric spaces with costly distance measures, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1231-1251, August 2008
G. Boccignone , A. Chianese , V. Moscato , A. Picariello, Context-sensitive queries for image retrieval in digital libraries, Journal of Intelligent Information Systems, v.31 n.1, p.53-84, August 2008
Rodrigo Paredes , Nora Reyes, Solving similarity joins and range queries in metric spaces with the list of twin clusters, Journal of Discrete Algorithms, v.7 n.1, p.18-35, March, 2009

INDEX TERMS

Keywords:
best match, file searching, file structuring, heuristics, matching

Collaborative Colleagues:
W. A. Burkhard: colleagues
R. M. Keller: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player