On finding the closest bitwise matches in a fixed set

ABSTRACT

In a given large fixed table of bit-vectors, we would like to find, as rapidly as possible, those bit-vectors which have the least Hamming distances from a newly-presented arbitrary bit-vector.

REFERENCES

• 1: Michael Beeler , R. W Gosper , Rich Schroeppel, HAKMEM, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 2: 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 [doi>10.1145/355744.355745]
• 3: Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
• 4: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• 5: EASTMAN, C. M. AND WEISS, S.F. Tree structures for high dimensionality nearest neighbor searching. Inf. Syst. 7, 2 (1982), 115-122.
• 6: C. Faloutsos, Gray Codes for Partial Match and Range Queries, IEEE Transactions on Software Engineering, v.14 n.10, p.1381-1393, October 1988 [doi>10.1109/32.6184]
• 7: FRIEDMAN, J. H., BASKETT, F., AND SHUSTEK, L. J. An algorithm for finding nearest neighbors. IEEE Trans. Comput. 24, 10 (Oct. 1975), 1000-1006.
• 8: FUKUNAGA, K., AND NARENDRA, P. M. A branch and bound algorithm for computing k-nearest neighbors. IEEE Trans. Comput. 24, 7 (July 1975), 750-753.
• 9: KLIER, P. A de,~ign for automated integral tables. M.S. thesis, Dept. Electrical Engineering and Computer Sciences, University of California at Berkeley, May 1989.
• 10: Harry R. Lewis , Christos H. Papadimitriou , Christos Papadimitriou, Elements of the Theory of Computation, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 11: NmSSON, N. J. Principles of Artificial Intelligence. Tioga Publishing, Palo Alto, Calif., 1980, pp.72-88.
• 12: OMOHUNDRO, S. M. Efficient algorithms with neural network behavior. Tech. Rept. UIUCDCS-R-87-1331, Dept. Computer Science, University of Illinois at Urbana-Champaign, April 1987.
• 13: PETERSON, W. W., AND WELDON, E. J. Error-Correcting Codes. MIT Press, Cambridge, Mass., 1972.
• 14: RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comput. 5, I (March 1976), 19-50.
• 15: STALLMAN, R.M. The Gnu CC Compiler, version 1.22. Free Software Foundation, Cambr~clge, Mass., 1'9~9.
• 16: Patrick Henry Winston, Artificial intelligence (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance

Keywords:
Hamming distance, K-d trees, bit-vectors, hash-table, high-dimension search, pattern matching, search