{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:10:25Z","timestamp":1725484225162},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_38","type":"book-chapter","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T21:12:57Z","timestamp":1180213977000},"page":"439-450","source":"Crossref","is-referenced-by-count":3,"title":["One-Probe Search"],"prefix":"10.1007","author":[{"given":"Anna","family":"\u00d6stlin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Arne Andersson and Mikkel Thorup. Tight (er) worst-case bounds on dynamic searching and priority queues. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC\u2019 00), pages 335\u2013342. ACM Press, 2000.","DOI":"10.1145\/335305.335344"},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"Paul Beame and Faith Fich. Optimal bounds for the predecessor problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC\u2019 99), pages 295\u2013304. ACM Press, 1999.","DOI":"10.1145\/301250.301323"},{"key":"38_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-48447-7_34","volume-title":"Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS\u2019 99)","author":"G. S. Brodal","year":"1999","unstructured":"Gerth St\u00f8lting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS\u2019 99), volume 1663 of Lecture Notes in Computer Science, pages 342\u2013351. Springer-Verlag, 1999."},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Peter BroMiltersen, Jaikumar Radhakrishnan, and S. Venkatesh. Are bitvectors optimal? In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC\u2019 00), pages 449\u2013458. ACM Press, 2000.","DOI":"10.1145\/335305.335357"},{"key":"38_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BFb0032018","volume-title":"Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP\u2019 90)","author":"M. Dietzfelbinger","year":"1990","unstructured":"Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP\u2019 90), volume 443 of Lecture Notes in Computer Science, pages 6\u201319. Springer-Verlag, 1990."},{"issue":"1","key":"38_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0222001","volume":"22","author":"A. Fiat","year":"1993","unstructured":"Amos Fiat and Moni Naor. Implicit O(1) probe search. SIAM J. Comput., 22(1):1\u201310, 1993.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"38_CR7","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"Michael L. Fredman, J\u00e1nos Koml\u00f3s, and Endre Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach., 31(3):538\u2013544, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"38_CR8","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. L. Fredman","year":"1993","unstructured":"Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci., 47:424\u2013436, 1993.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"38_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh. Deterministic dictionaries. J. Algorithms, 41(1):69\u201385, 2001.","journal-title":"J. Algorithms"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P. Hall","year":"1935","unstructured":"Philip Hall. On representatives of subsets. J. London Math. Soc., 10:26\u201330, 1935.","journal-title":"J. London Math. Soc."},{"issue":"2","key":"38_CR11","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0022-0000(80)90037-9","volume":"21","author":"J. Ian Munro","year":"1980","unstructured":"J. Ian Munro and Hendra Suwanda. Implicit data structures for fast search and update. J. Comput. System Sci., 21(2):236\u2013250, 1980.","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"38_CR12","first-page":"151","volume":"7","author":"R. Pagh","year":"2000","unstructured":"Rasmus Pagh. A trade-off for worst-case efficient dictionaries. Nordic J. Comput., 7(3):151\u2013163, 2000.","journal-title":"Nordic J. Comput."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Rasmus Pagh. On the Cell Probe Complexity of Membership and Perfect Hashing. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC\u2019 01), pages 425\u2013432. ACM Press, 2001. http:\/\/www.brics.dk\/ pagh\/papers\/probe.pdf","DOI":"10.1145\/380752.380836"},{"key":"38_CR14","unstructured":"Amnon Ta-Shma. Storing information with extractors. To appear in Information Processing Letters."},{"key":"38_CR15","doi-asserted-by":"crossref","unstructured":"Amnon Ta-Shma, Christopher Umans, and David Zuckerman. Loss-less condensers, unbalanced expanders, and extractors. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC\u2019 01), pages 143\u2013152. ACM Press, 2001.","DOI":"10.1145\/380752.380790"},{"issue":"3","key":"38_CR16","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A. C.-C. Yao","year":"1981","unstructured":"Andrew C.-C. Yao. Should tables be sorted? J. Assoc. Comput. Mach., 28(3):615\u2013628, 1981.","journal-title":"J. Assoc. Comput. Mach."}],"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-45465-9_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T07:05:53Z","timestamp":1556435153000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}