Some approaches to best-match file searching
Authors:
Open Access
- 1 April 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 16 (4) , 230-236
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.Keywords
This publication has 6 references indexed in Scilit:
- Corrections to Bierstone's Algorithm for Generating CliquesJournal of the ACM, 1972
- An Analysis of Some Graph Theoretical Cluster TechniquesJournal of the ACM, 1970
- All-automatic processing for a large library1970
- Theory of transformation groups of polynomials over GF(2) with applications to linear shift register sequencesInformation Sciences, 1968
- Scatter storage techniquesCommunications of the ACM, 1968
- Methods of Interpreting Diagnostic Data for Locating Faults in Digital MachinesBell System Technical Journal, 1967