Monotone minimal perfect hashing: searching a sorted table with O(1) accesses

ABSTRACT

A minimal perfect hash function maps a set S of n keys into the set {0, 1,..., n -- 1} bijectively. Classical results state that minimal perfect hashing is possible in constant time using a structure occupying space close to the lower bound of log e bits per element. Here we consider the problem of monotone minimal perfect hashing, in which the bijection is required to preserve the lexicographical ordering of the keys. A monotone minimal perfect hash function can be seen as a very weak form of index that provides ranking just on the set S (and answers randomly outside of S). Our goal is to minimise the description size of the hash function: we show that, for a set S of n elements out of a universe of 2w elements, O(n log log w) bits are sufficient to hash monotonically with evaluation time O(log w). Alternatively, we can get space O(n log w) bits with O(1) query time. Both of these data structures improve a straightforward construction with O(n log w) space and O(log w) query time. As a consequence, it is possible to search a sorted table with O(1) accesses to the table (using additional O(n log log w) bits). Our results are based on a structure (of independent interest) that represents a trie in a very compact way, but admits errors. As a further application of the same structure, we show how to compute the predecessor (in the sorted order of S) of an arbitrary element, using O(1) accesses in expectation and an index of O(n log w) bits, improving the trivial result of O(n w) bits. This implies an efficient index for searching a blocked memory.

REFERENCES

• 1: Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Journal of Algorithms, v.53 n.2, p.115-136, November 2004 [doi>10.1016/j.jalgor.2004.04.014]
• 2: Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob, Cache oblivious search trees via binary trees of small height, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-48, January 06-08, 2002, San Francisco, California
• 3: J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143--154, 1979.
• 4: Larry Carter , Robert Floyd , John Gill , George Markowsky , Mark Wegman, Exact and approximate membership testers, Proceedings of the tenth annual ACM symposium on Theory of computing, p.59-65, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804332]
• 5: Denis Charles , Kumar Chellapilla, Bloomier Filters: A Second Look, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_22]
• 6: David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
• 7: Martin Dietzfelbinger , Joseph Gil , Yossi Matias , Nicholas Pippenger, Polynomial Hash Functions Are Reliable (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.235-246, July 13-17, 1992
• 8: Martin Dietzfelbinger , Rasmus Pagh, Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract), Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_32]
• 9: Amos Fiat , Moni Naor, Implicit O(1) probe search, SIAM Journal on Computing, v.22 n.1, p.1-10, Feb. 1993 [doi>10.1137/0222001]
• 10: Amos Fiat , Moni Naor , Jeanette P. Schmidt , Alan Siegel, Nonoblivious hashing, Journal of the ACM (JACM), v.39 n.4, p.764-782, Oct. 1992 [doi>10.1145/146585.146591]
• 11: 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]
• 12: M. L. Fredman and J. Komlós. On the size of separating systems and families of perfect hash functions. SIAM J. Algebraic Discrete Methods, 5(1):61--68, 1984.
• 13: 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]
• 14: Ankur Gupta , Wing-Kai Hon , Rahul Shah , Jeffrey Scott Vitter, Compressed data structures: Dictionaries and data-aware measures, Theoretical Computer Science, v.387 n.3, p.313-331, November, 2007 [doi>10.1016/j.tcs.2007.07.042]
• 15: Torben Hagerup , Torsten Tholey, Efficient Minimal Perfect Hashing in Nearly Minimal Space, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.317-326, February 15-17, 2001
• 16: G. Jacobson, Space-efficient static trees and graphs, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.549-554, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63533]
• 17: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 18: Harry G. Mairson, The program complexity of searching a table, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.40-47, November 07-09, 1983 [doi>10.1109/SFCS.1983.76]
• 19: Harry G. Mairson, The effect of table expansion on the program complexity of perfect hash functions, BIT, v.32 n.3, p.430-440, 1992 [doi>10.1007/BF02074879]
• 20: B. S. Majewski, N. C. Wormald, G. Havas, and Z. J. Czech. A family of perfect hashing methods. Comput. J., 39(6):547--554, 1996.
• 21: Kurt Mehlhorn, On the program size of perfect and universal hash functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.170-175, November 03-05, 1982
• 22: Rasmus Pagh, Low Redundancy in Static Dictionaries with Constant Query Time, SIAM Journal on Computing, v.31 n.2, p.353-363, 2001 [doi>10.1137/S0097539700369909]
• 23: E. Porat. An optimal bloom filter replacement based on matrix solving, 2008. arXiv:0804.1845v1.
• 24: Vijayshankar Raman, Locality preserving dictionaries: theory & application to clustering in databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.337-345, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304009]
• 25: Jeanette P. Schmidt , Alan Siegel, The spatial complexity of oblivious k-probe Hash functions, SIAM Journal on Computing, v.19 n.5, p.775-786, Oct. 1990 [doi>10.1137/0219054]
• 26: D. E. Willard. Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett., 17(2):81--84, 1983.
• 27: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms