W. A. Burkhard
R. M. Keller
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.
- 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.Google Scholar
Cross Ref
- 2 Wipke, W.T. Private communication. Dep. of Chem., Princeton U., Princeton, N.J.Google Scholar
- 3 Minsky, M., and Papert, S. Perceptrons: An Introduction to Computational Geometry M.I.T. Press, Cambridge, Mass., 1969. Google ScholarDigital Library
- 4 Morris, R. Scatter storage techniques. Comm. ACM, 11, (1 Jan. 1968), 38-44. Google ScholarDigital Library
- 5 Jackson, D.M. Classification, relevance, and information retrieval. Advances in Computers Vol. 11, Academic Press, N.Y., 1971.Google Scholar
- 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.Google Scholar
- 7 Salton, G. Experiments in automatic thesaurus construction for information retrieval. Proc. IFIP Congress 1971, North Holland Pub. Co., Amsterdam.Google Scholar
- 8 Augustson, J.G., and Minker, J. An analysis of some graph theoretical cluster techniques. J. ACM 17, 4 (Oct. 1970), 571-588. Google ScholarDigital Library
- 9 Mulligan, C.D., and Corneil, D.G. Corrections to Bierstone's algorithm for generating cliques. J. ACM 19, 2 (Apr. 1972), 244-247. Google ScholarDigital Library
- 10 Golomb, S.W. Shift Register Sequences. Holden-Day, Inc., San Francisco, 1967. Google ScholarDigital Library
- 11 Bron, C., and Kerbosh, J.A.G.M. Finding all cliques of an undirected graph. (To be published.)Google Scholar
Recommendations
The choice of reference points in best-match file searching
Improvements to the exhaustive search method of best-match file searching have previously been achieved by doing a preprocessing step involving the calculation of distances from a reference point. This paper discusses the proper choice of reference ...
Interactive file searching using file metadata and visualization
BCS '10: Proceedings of the 24th BCS Interaction Specialist Group ConferenceNavigation and browsing on a computer system are usually done using the file system hierarchy. However, this is not the most adequate method to search or locate a given file at a later time, unless we know exactly where it is. In this paper, we present ...
Comments