{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T04:02:09Z","timestamp":1791172929896,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540404934","type":"print"},{"value":"9783540450610","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_30","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"357-368","source":"Crossref","is-referenced-by-count":49,"title":["Succinct Dynamic Dictionaries and Trees"],"prefix":"10.1007","author":[{"given":"Rajeev","family":"Raman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satti Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"30_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-48447-7_4","volume-title":"Proc. WADS\u2019 99","author":"A. Brodnik","year":"1999","unstructured":"A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro and R. Sedgewick. Resizable arrays in optimal time and space. In Proc. WADS\u2019 99, LNCS 1663, 37\u201348."},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"1628","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"A. Brodnik and J. I. Munro. Membership in constant time and almost minimum space. SIAM J. Computing\n                           28 (1999), 1628\u20131640.","journal-title":"SIAM J. Computing"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1109\/TC.1984.1676499","volume":"9","author":"J. G. Cleary","year":"1984","unstructured":"J. G. Cleary. Compact hash tables using bidirectional linear probing. IEEE Trans. Comput.\n                           9 (1984), 828\u2013834.","journal-title":"IEEE Trans. Comput."},{"key":"30_CR4","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms, The MIT Press, Cambridge, MA, 1990."},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"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\u2013761.","journal-title":"SIAM J. Computing"},{"key":"30_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/3-540-36494-3_25","volume-title":"Proc. 20th STACS","author":"D. Fotakis","year":"2003","unstructured":"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\u2013282, 2003."},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. J. ACM, 31 (1984), 538\u2013544.","journal-title":"J. ACM"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM STOC, 345\u2013354, 1989.","DOI":"10.1145\/73007.73040"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"R. Grossi and J. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. Proc. 32nd ACM STOC, 397\u2013406, 2000.","DOI":"10.1145\/335305.335351"},{"key":"30_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"Proc. 15th STACS","author":"T. Hagerup","year":"1998","unstructured":"T. Hagerup. Sorting and searching on the word RAM. In Proc. 15th STACS, LNCS 1373, 366\u2013398, 1998."},{"key":"30_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/3-540-56939-1_77","volume-title":"Proc. 20th ICALP","author":"T. Hagerup","year":"1993","unstructured":"T. Hagerup, K. Mehlhorn and J. I. Munro. Maintaining discrete probability distributions optimally. In Proc. 20th ICALP, LNCS 700, 253\u2013264, 1993."},{"key":"30_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-45993-6","volume-title":"Proc. 8th SWAT","author":"T. Hagerup","year":"2002","unstructured":"T. Hagerup and R. Raman. An efficient quasidictionary. In Proc. 8th SWAT, LNCS 2368, 1\u201318, 2002."},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"G. Jacobson. Space efficient static trees and graphs. In Proc. 30th IEEE Symp. FOCS, 549\u2013554, 1989.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"J. I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In Proc. 37th IEEE Symp. FOCS, 118\u2013126, 1997.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"30_CR15","unstructured":"J. I. Munro, V. Raman and A. Storm. Representing dynamic binary trees succinctly. In Proc. 12th ACM-SIAM SODA, 529\u2013536, 2001."},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. Comput, 31 (2001), 353\u2013363.","journal-title":"SIAM J. Comput"},{"key":"30_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-44676-1_10","volume-title":"Proc. 9th ESA","author":"R. Pagh","year":"2001","unstructured":"R. Pagh and F. F. Rodler. Cuckoo Hashing. Proc. 9th ESA, LNCS 2161, 121\u2013133, 2001."},{"key":"30_CR18","unstructured":"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\u2013242, 2002."},{"key":"30_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/3-540-44634-6_39","volume-title":"Proc. 7th WADS","author":"R. Raman","year":"2001","unstructured":"R. Raman, V. Raman and S. S. Rao. Succinct dynamic data structures. In Proc. 7th WADS, LNCS 2125, 426\u2013437, 2001."},{"key":"30_CR20","unstructured":"A. Silberschatz, P. B. Galvin and G. Gagne. Operating System Concepts, 6th ed. John Wiley & Sons, 2001."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T23:21:51Z","timestamp":1550445711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}