Some Approaches to Best-Match File Searching

Authors

Walter A. Burkhard, University of California - San Diego
Robert M. Keller, Harvey Mudd CollegeFollow

Document Type

Article

Department

Computer Science (HMC)

Publication Date

4-1973

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.

Rights Information

©1973 Association for Computing Machinery

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Burkhard, WA, Keller, RM. Some approaches to best-match file searching. Comm ACM. 1973;16(4): 230-236.