Dictionaries using variable-length keys and data, with applications

ABSTRACT

We consider the problem of maintaining a dynamic dictionary in which both the keys and the associated data are variable-length bit-strings. We present a dictionary structure based on hashing that supports constant time lookup and expected amortized constant time insertion and deletion. To store the key-data pairs (s1, t1) ... (sn, tn), our dictionary structure uses O(m) bits where m = Σ(max(|si| -- log n, 1) + |ti| and |si| is the length of bit string si. We assume a word length w > log m.We present several applications, including representations for semi-dynamic graphs, ordered sets for integers in a bounded range, cardinal trees with varying cardinality, and simplicial meshes of k dimensions. These results either generalize or simplify previous results.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: David Benoit , Erik D. Demaine , J. Ian Munro , Venkatesh Raman, Representing Trees of Higer Degree, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.169-180, August 11-14, 1999
• 3: Daniel K. Blandford , Guy E. Blelloch, Compact representations of ordered sets, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 4: Daniel K. Blandford , Guy E. Blelloch , Ian A. Kash, Compact representations of separable graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: D. Blandford, G. Blelloch, and I. Kash. An experimental analysis of a compact graph representation. In ALENEX04, 2004.
• 6: D. K. Blandford, G. E. Blelloch, D. E. Cardoze, and C. Kadow. Compact representations of simplicial meshes in two and three dimensions. In Proc. International Meshing Roundtable (IMR), Sept. 2003.
• 7: Guy E. Blelloch , Bruce M. Maggs , Shan Leung Maverick Woo, Space-efficient finger search on degree-balanced search trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Andrej Brodnik , J. Ian Munro, Membership in Constant Time and Almost-Minimum Space, SIAM Journal on Computing, v.28 n.5, p.1627-1640, April/May 1999 [doi>10.1137/S0097539795294165]
• 9: L. Carter and M. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, pages 143--154, 1979.
• 10: Richie Chih-Nan Chuang , Ashim Garg , Xin He , Ming-Yang Kao , Hsueh-I Lu, Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.118-129, July 13-17, 1998
• 11: J. G. Cleary. Compact hash tables using bidirectional linear probing. IEEE Trans. Comput, 9:828--834, 1984.
• 12: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 13: Geometry and topology for mesh generation, Cambridge University Press, New York, NY, 2001
• 14: P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, IT-21(2):194--203, March 1975.
• 15: Dimitris Fotakis , Rasmus Pagh , Peter Sanders , Paul G. Spirakis, Space Efficient Hash Tables with Worst Case Constant Access Time, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.271-282, February 27-March 01, 2003
• 16: 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]
• 17: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 18: Xin He , Ming-Yang Kao , Hsueh-I Lu, A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs, SIAM Journal on Computing, v.30 n.3, p.838-846, 2000 [doi>10.1137/S0097539799359117]
• 19: G. Jacobson. Space-efficient static trees and graphs. In 30th FOCS, pages 549--554, 1989.
• 20: Kenneth Keeler , Jeffery Westbrook, Short encodings of planar graphs and maps, Discrete Applied Mathematics, v.58 n.3, p.239-252, April 7, 1995 [doi>10.1016/0166-218X(93)E0150-W]
• 21: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 22: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 23: J. I. Munro , V. Raman, Succinct representation of balanced parentheses, static trees and planar graphs, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.118, October 19-22, 1997
• 24: Rasmus Pagh, Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.595-604, July 11-15, 1999
• 25: 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]
• 26: Rasmus Pagh , Flemming Friche Rodler, Cuckoo Hashing, Proceedings of the 9th Annual European Symposium on Algorithms, p.121-133, August 28-31, 2001
• 27: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California
• 28: R. Raman and S. S. Rao. Succinct dynamic dictionaries and trees. In ICALP, pages 357--36, 2003.
• 29: G. Turán. Succinct representations of graphs. Discrete Applied Mathematics, 8:289--294, 1984.