{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T01:47:16Z","timestamp":1743731236900},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584346"},{"type":"electronic","value":"9783540487944"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0049398","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T13:42:35Z","timestamp":1141652555000},"page":"72-81","source":"Crossref","is-referenced-by-count":10,"title":["Membership in constant time and minimum space"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Brodnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. In Proceedings 19 th International Colloquium on Automata, Languages and Programming, volume 623 of Lecture Notes in Computer Science, pages 235\u2013246. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"8_CR2","doi-asserted-by":"crossref","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. In 29 th IEEE Symposium on Foundations of Computer Science, pages 524\u2013531, 1988.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proceedings 17 th International Colloquium on Automata, Languages and Programming, volume 443 of Lecture Notes in Computer Science, pages 6\u201319. Springer-Verlag, 1990.","DOI":"10.1007\/BFb0032018"},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P. Elias","year":"1974","unstructured":"P. Elias. Efficient storage retrieval by content and address of static files. Journal of the ACM, 21(2):246\u2013260, April 1974.","journal-title":"Journal of the ACM"},{"issue":"3","key":"8_CR5","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1145\/321892.321899","volume":"22","author":"P. Elias","year":"1975","unstructured":"P. Elias and R.A. Flower. The complexity of some simple retrieval problems. Journal of the ACM, 22(3):367\u2013379, July 1975.","journal-title":"Journal of the ACM"},{"key":"8_CR6","series-title":"volume A: Algorithms and Complexity","first-page":"1","volume-title":"Handbook of Theoretical Computer Science","author":"P. Emde Boas van","year":"1990","unstructured":"P. van Emde Boas. Machine models and simulations. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, chapter 1, pages 1\u201366. Elsevier, Amsterdam, Holland, 1990."},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0222001","volume":"22","author":"A. Fiat","year":"1993","unstructured":"A. Fiat and M. Naor. Implicit O(1) probe search. SIAM Journal on Computing, 22(1):1\u201310, 1993.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1145\/146585.146591","volume":"39","author":"A. Fiat","year":"1992","unstructured":"A. Fiat, M. Naor, J.P. Schmidt, and A. Siegel. Nonoblivious hashing. Journal of the ACM, 39(4):764\u2013782, October 1992.","journal-title":"Journal of the ACM"},{"issue":"3","key":"8_CR9","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. Journal of the ACM, 31(3):538\u2013544, July 1984.","journal-title":"Journal of the ACM"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"M.L. Fredman and M.E. Saks. The cell probe complexity of dynamic data structures. In 21 st ACM Symposium on Theory of Computing, pages 345\u2013354, Seattle, Washington, 1989.","DOI":"10.1145\/73007.73040"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30:209\u2013221, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"T. Hagerup, K. Mehlhorn, and J.I. Munro. Optimal algorithms for generating discrete random variables with changing distributions. In Proceedings 20th International Colloquium on Automata, Languages and Programming, volume 700 of Lecture Notes in Computer Science, pages 253\u2013264. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-56939-1_77"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"P.B. Miltersen. The bit probe complexity measure revisited. In Proceedings 10 th Symposium on Theoretical Aspects of Computer Science, volume 665 of Lecture Notes in Computer Science, pages 662\u2013671. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-56503-5_65"},{"issue":"11","key":"8_CR14","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/359168.359175","volume":"22","author":"R.E. Tarjan","year":"1979","unstructured":"R.E. Tarjan and A.C. Yao. Storing a sparse table. Communications of the ACM, 22(11):606\u2013611, November 1979.","journal-title":"Communications of the ACM"},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C.-C. Yao","year":"1981","unstructured":"A.C.-C. Yao. Should tables be sorted? Journal of the ACM, 28(3):614\u2013628, July 1981.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T01:56:16Z","timestamp":1555466176000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0049398","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}