{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:24:12Z","timestamp":1725495852763},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540669166"},{"type":"electronic","value":"9783540466321"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46632-0_3","type":"book-chapter","created":{"date-parts":[[2007,11,24]],"date-time":"2007-11-24T14:45:01Z","timestamp":1195915501000},"page":"18-26","source":"Crossref","is-referenced-by-count":3,"title":["Static Dictionaries Supporting Rank"],"prefix":"10.1007","author":[{"given":"Venkatesh","family":"Raman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02126797","volume":"8","author":"M. Ajtai","year":"1988","unstructured":"M. Ajtai, \u201cA lower bound for finding predecessors in Yao\u2019s cell probe model\u201d, Combinatorica 8 (1988) 235\u2013247.","journal-title":"Combinatorica"},{"key":"3_CR2","unstructured":"D. Benoit, \u201cCompact Tree Representations\u201d, Master\u2019s Thesis, Department of Computer Science, University of Waterloo, Canada (1998)."},{"key":"3_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/3-540-48447-7_18","volume-title":"The Proceedings of the 6th International Workshop on Algorithms and Data Structures","author":"D. Benoit","year":"1999","unstructured":"D. Benoit, E. D. Demaine, J. I. Munro and V. Raman \u201cRepresenting Trees of Higher Degree\u201d, The Proceedings of the 6th International Workshop on Algorithms and Data Structures, Springer Verlag Lecture Notes in Computer Science 1663 (1999) 169\u2013180."},{"key":"3_CR4","unstructured":"A. Brodnik and J. I. Munro, \u201cMembership in constant time and almost minimum space\u201d, to appear in SIAM Journal on Computing."},{"key":"3_CR5","unstructured":"D. R. Clark, \u201cCompact Pat Trees\u201d, Ph.D. Thesis, University of Waterloo, 1996."},{"key":"3_CR6","unstructured":"D. R. Clark and J. I. Munro, \u201cEfficient Suffix Trees on Secondary Storage\u201d, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (1996) 383\u2013391."},{"issue":"4","key":"3_CR7","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1145\/146585.146591","volume":"39","author":"A. Fiat","year":"1992","unstructured":"A. Fiat, M. Noar, J. P. Schmidt and A. Siegel, \u201cNon-oblivious hashing\u201d, Journal of the Association for Computing Machinery, 39(4) (1992) 764\u2013782.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR8","doi-asserted-by":"crossref","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, \u201cStoring a sparse table with O(1) access time\u201d, Journal of the Association for Computing Machinery, 31 (1984) 538\u2013544.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"G. Jacobson, \u201cSpace-efficient Static Trees and Graphs\u201d, Proceedings of the IEEE Symposium on Foundations of Computer Science (1989) 549\u2013554.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"3_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Proceedings of the 16th FST & TCS conference","author":"J. I. Munro","year":"1996","unstructured":"J. I. Munro, \u201cTables\u201d, Proceedings of the 16th FST & TCS conference, Springer Verlag Lecture Notes in Computer Science 1180 (1996) 37\u201342."},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"J. I. Munro and V. Raman, \u201cSuccinct representation of balanced parentheses, static trees and planar graphs\u201d, Proceedings of the IEEE Symposium on Foundations of Computer Science (1997) 118\u2013126.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Rasmus Pagh, \u201cLow redundancy in dictionaries with O(1) worst case lookup time\u201d, to appear in Proceedings of the International Colloquium on Automata, Languages and Programming (1999).","DOI":"10.1007\/3-540-48523-6_56"},{"issue":"5","key":"3_CR13","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J. P. Schmidt","year":"1990","unstructured":"J. P. Schmidt and A. Siegel, \u201cThe spatial complexity of oblivious k-probe hash functions\u201d, SIAM Journal on Computing 19(5) (1990) 775\u2013786.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. E. Willard","year":"1983","unstructured":"D. E. Willard, \u201cLog-Logarithmic worst case range queries are possible in space _(n)\u201d, Information Processing Letters 17 (1983) 81\u201389.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46632-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T22:04:35Z","timestamp":1557007475000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46632-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540669166","9783540466321"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-46632-0_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}