Abstract
We consider space-efficient solutions to two dynamic data structuring problems. We first give a representation of a set \( S \subseteq U = \left\{ {0,...,m - 1} \right\},\left| S \right| = n \) that supports membership queries in O(1) worst case time and insertions into/deletions from S in O(1) expected amortised time. The representation uses \( \mathcal{B} + o\left( \mathcal{B} \right) \) bits, where \( \mathcal{B} = \left\lceil {\lg \left( \begin{gathered} m \hfill \\ n \hfill \\ \end{gathered} \right)} \right\rceil \) is the information-theoretic minimum space to represent S. This improves upon the O(\( \left( \mathcal{B} \right) \))-bit solutions of Brodnik and Munro [2] and Pagh [16], and uses up to a log-factor less space than search trees or hash tables. The representation can also associate satellite data with elements of S.
We also show that a binary tree on n nodes, where each node has b = O(lg n)-bit data stored at it, can be maintained under node insertions while supporting navigation in O(1) time and updates in O((lg lg n)1+∈) amortised time, for any constant ∈ > 0. The space used is within o(n) bits of the information-theoretic minimum. This improves upon the equally space-efficient structure of Munro et al. [15], in which updates take O(lgc n) time, for some c ≥ 1.
Supported in part by UISTRF project 2001.04/IT and EPSRC GR L/92150.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro and R. Sedgewick. Resizable arrays in optimal time and space. In Proc. WADS’ 99, LNCS 1663, 37–48.
A. Brodnik and J. I. Munro. Membership in constant time and almost minimum space. SIAM J. Computing 28 (1999), 1628–1640.
J. G. Cleary. Compact hash tables using bidirectional linear probing. IEEE Trans. Comput. 9 (1984), 828–834.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms, The MIT Press, Cambridge, MA, 1990.
M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert and R. E. Tarjan. Dynamic perfect hashing: upper and lower bounds. SIAM J. Computing, 23 (1994), 738–761.
D. Fotakis, R. Pagh, P. Sanders and P. Spirakis. Space efficient hash tables with worst case constant access time. In Proc. 20th STACS, LNCS 2607, 271–282, 2003.
M. L. Fredman, J. Komlós and E. Szemerédi. Storing a sparse table with O(1) worst case access time. J. ACM, 31 (1984), 538–544.
M. L. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM STOC, 345–354, 1989.
R. Grossi and J. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. Proc. 32nd ACM STOC, 397–406, 2000.
T. Hagerup. Sorting and searching on the word RAM. In Proc. 15th STACS, LNCS 1373, 366–398, 1998.
T. Hagerup, K. Mehlhorn and J. I. Munro. Maintaining discrete probability distributions optimally. In Proc. 20th ICALP, LNCS 700, 253–264, 1993.
T. Hagerup and R. Raman. An efficient quasidictionary. In Proc. 8th SWAT, LNCS 2368, 1–18, 2002.
G. Jacobson. Space efficient static trees and graphs. In Proc. 30th IEEE Symp. FOCS, 549–554, 1989.
J. I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In Proc. 37th IEEE Symp. FOCS, 118–126, 1997.
J. I. Munro, V. Raman and A. Storm. Representing dynamic binary trees succinctly. In Proc. 12th ACM-SIAM SODA, 529–536, 2001.
R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. Comput, 31 (2001), 353–363.
R. Pagh and F. F. Rodler. Cuckoo Hashing. Proc. 9th ESA, LNCS 2161, 121–133, 2001.
R. Raman, V. Raman and S. S. Rao. Succinct indexable dictionaries, with applications to representing k-ary trees and multisets. In Proc. 13th ACM-SIAM SODA, 233–242, 2002.
R. Raman, V. Raman and S. S. Rao. Succinct dynamic data structures. In Proc. 7th WADS, LNCS 2125, 426–437, 2001.
A. Silberschatz, P. B. Galvin and G. Gagne. Operating System Concepts, 6th ed. John Wiley & Sons, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Raman, R., Rao, S.S. (2003). Succinct Dynamic Dictionaries and Trees. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol 2719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45061-0_30
Download citation
DOI: https://doi.org/10.1007/3-540-45061-0_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40493-4
Online ISBN: 978-3-540-45061-0
eBook Packages: Springer Book Archive