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 for strings - 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 log log n) on a word RAM, and a static predecessor structure for variable-length binary strings with a query performance of O(|s|/B + log |s| + log log n) I/Os, for query argument s, in the cache-oblivious model.

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 (FOCS'95), 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?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225173]
• 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, 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]
• 10: 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
• 11: P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. J. Royal Statistical Society, 39:262--268, 1977.
• 12: 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
• 13: 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]
• 14: R. Fagerberg, A. Pagh, and R. Pagh. External string sorting: Faster and cache-oblivious. In 23rd STACS, pages 68--79, 2006.
• 15: 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]
• 16: 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]
• 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: 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]
• 19: 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
• 20: 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
• 21: 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
• 22: 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 ]
• 23: 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]
• 24: J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. In 30th ICALP, pages 943--955, 2003.
• 25: 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]
• 26: M. Ružić. Uniform deterministic dictionaries. Manuscript, 2005. Very preliminary version appeared as: Uniform Algorithms for Deterministic Construction of Efficient Dictionaries. In 12th ESA, pages 592--603. Springer-Verlag, 2004.
• 27: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory, 10:99--127, 1977.