Making deterministic signatures quickly

ABSTRACT

We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the word RAM, the practical RAM, and the cache-oblivious model. All algorithms and data structures are deterministic and use linear space. Representative results are: a dictionary with a lookup time of O(log log n) and construction time of O(n) on sorted input on a word RAM, and a static predecessor structure for variable- and unbounded length binary strings that in the cache-oblivious model has a query performance of O(|s|/B + log |s|) I/Os, for query argument s.

REFERENCES

• 1: Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.463-472, September 1992, Orlando, Florida, United States
• 2: A. Andersson, Sublogarithmic searching without multiplications, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.655, October 23-25, 1995
• 3: A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
• 4: Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Journal of Computer and System Sciences, v.57 n.1, p.74-93, Aug. 1998 [doi>10.1006/jcss.1998.1580]
• 5: A. Andersson, Static Dictionaries on RAMs: Query Time is Necessary and Sufficient, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.441, October 14-16, 1996
• 6: Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258647]
• 7: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 8: Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul, Cache-oblivious string B-trees, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142385]
• 9: Gerth Stølting Brodal , Rolf Fagerberg, On the limits of cache-obliviousness, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780589]
• 10: Gerth Stølting Brodal , Rolf Fagerberg, Cache-oblivious string dictionaries, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.581-590, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109621]
• 11: Andrej Brodnik , Peter Bro Miltersen , J. Ian Munro, Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.426-439, August 06-08, 1997
• 12: Diaconis, P., and Graham, R. L. 1977. Spearman's footrule as a measure of disarray. J. Royal Statist. Soc. 39, 262--268.
• 13: Paul F. Dietz, Optimal Algorithms for List Indexing and Subset Rank, Proceedings of the Workshop on Algorithms and Data Structures, p.39-46, August 17-19, 1989
• 14: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm Meyer auf der Heide , Hans Rohnert , Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 15: Fagerberg, R., Pagh, A., and Pagh, R. 2006. External string sorting: Faster and cache-oblivious. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 3884. Springer, 68--79.
• 16: Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
• 17: 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]
• 18: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 19: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 20: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 21: Torben Hagerup, Simpler and Faster Dictionaries on the AC0 RAM, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.79-90, July 13-17, 1998
• 22: Torben Hagerup, Sorting and Searching on the Word RAM, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.366-398, February 25-27, 1998
• 23: Torben Hagerup , Peter Bro Miltersen , Rasmus Pagh, Deterministic dictionaries, Journal of Algorithms, v.41 n.1, p.69-85, October 2001 [doi>10.1006/jagm.2001.1171]
• 24: Yijie Han, Deterministic sorting in O(nlog logn) time and linear space, Journal of Algorithms, v.50 n.1, p.96-105, January 2004 [doi>10.1016/j.jalgor.2003.09.001]
• 25: Kärkkäinen, J., and Sanders, P. 2003. Simple linear work suffix array construction. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719. Springer, 943--955.
• 26: Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132551]
• 27: Rajeev Raman, Priority Queues: Small, Monotone and Trans-dichotomous, Proceedings of the Fourth Annual European Symposium on Algorithms, p.121-137, September 25-27, 1996
• 28: Milan Ružić, Making deterministic signatures quickly, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.900-909, January 07-09, 2007, New Orleans, Louisiana
• 29: Milan Ružić, Constructing Efficient Dictionaries in Close to Sorting Time, 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_8]
• 30: Milan Ružić, Uniform deterministic dictionaries, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-23, March 2008 [doi>10.1145/1328911.1328912]
• 31: Mikkel Thorup, On AC⁰ implementations of fusion trees and atomic heaps, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 32: van Emde Boas, P., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99--127.

INDEX TERMS

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

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

General Terms:
Algorithms, Performance, Theory

Keywords:
Deterministic algorithms, perfect hashing