A faster algorithm for constructing minimal perfect hash functions

ABSTRACT

Our previous research on one-probe access to large collections of data indexed by alphanumeric keys has produced the first practical minimal perfect hash functions for this problem. Here, a new algorithm is described for quickly finding minimal perfect hash functions whose specification space is very close to the theoretical lower bound, i.e., around 2 bits per key. The various stages of processing are detailed, along with analytical and empirical results, including timing for a set of over 3.8 million keys that was processed on a NeXTstation in about 6 hours.

REFERENCES

• 1: Richard Barnhart. The Advanced Naval Message Analyzer. Videotape production, VPI&SU, November 1990. Richard Barnhart as host, producer, script-writer; Edward Fox as executive producer, project director. Discusses the CODER system.
• 2: N. Cercone, M. Krause, and J. Boates. Minimal and almost minimal perfect hash function search with application to natural language lexicon design. Computers and Mathematics with Applications, 9:215-231, 1983.
• 3: C C Chang, Letter-oriented reciprocal hashing scheme, Information Sciences: an International Journal, v.38 n.3, p.243-255, June 1986 [doi>10.1016/0020-0255(86)90024-1]
• 4: Qi Fan Chen. An object-oriented database system for efficient information retrieval applications. PhD thesis, Virginia Tech Dept. of Computer Science, March 1992.
• 5: Richard J. Cichelli, Minimal perfect hash functions made simple, Communications of the ACM, v.23 n.1, p.17-19, Jan. 1980 [doi>10.1145/358808.358813]
• 6: E. A. Fox and Robert K. France. Architecture of an expert system for composite document analysis, representation and retrieval. International Journal of Approximate Reasoning, 1(1): 151-175, 1987.
• 7: Edward A. Fox, Development of the CODER system: a testbed for artificial intelligence methods in information retrieval, Information Processing and Management: an International Journal, v.23 n.4, p.341-366, July 1987 [doi>10.1016/0306-4573(87)90022-7]
• 8: Edward A. Fox , Qi Fan Chen , Amjad M. Daoud , Lenwood S. Heath, Order-preserving minimal perfect hash functions and information retrieval, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.281-308, July 1991 [doi>10.1145/125187.125200]
• 9: Edward A. Fox , Lenwood S. Heath , Qi Fan Chen , Amjad M. Daoud, Practical minimal perfect hash functions for large databases, Communications of the ACM, v.35 n.1, p.105-121, Jan. 1992 [doi>10.1145/129617.129623]
• 10: Edward A. Fox , Prabhakar M. Koushik , Qi Chen , Robert K. France, Integrated Access to a Large Medical Literature Database, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1991
• 11: M.L. Fredman and J. Koml6s. On the size of separating systems and families of perfect hash functions. SIAM Journal on Algebraic and Discrete Methods', 5:61-68, 1984.
• 12: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 13: G. Jaeschke, Reciprocal hashing: a method for generating minimal perfect hashing functions, Communications of the ACM, v.24 n.12, p.829-833, Dec. 1981 [doi>10.1145/358800.358806]
• 14: K. Mehlhorn. On the program size of perfect and universal hash functions. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pages 170-175, 1982.
• 15: Peter K. Pearson, Fast hashing of variable-length text strings, Communications of the ACM, v.33 n.6, p.677-680, June 1990 [doi>10.1145/78973.78978]
• 16: Thomas J. Sager, A polynomial time generator for minimal perfect hash functions, Communications of the ACM, v.28 n.5, p.523-532, May 1985 [doi>10.1145/3532.3538]
• 17: M. Weaver, R. France, Q. Chen, and E. Fox. Using a frame-based language for information retrieval. International Journal of Intelligent Systems, 4(3):223-257, 1989.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  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.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Performance