{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:30:47Z","timestamp":1775899847199,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705741","type":"print"},{"value":"9783540705758","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_32","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"385-396","source":"Crossref","is-referenced-by-count":46,"title":["Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: Proc. 33rd ACM STOC, pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"issue":"7","key":"32_CR2","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"B.H. Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM\u00a013(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-540-73951-7_13","volume-title":"Algorithms and Data Structures","author":"F.C. Botelho","year":"2007","unstructured":"Botelho, F.C., Pagh, R., Ziviani, N.: Simple and space-efficient minimal perfect hash functions. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 139\u2013150. Springer, Heidelberg (2007)"},{"key":"32_CR4","first-page":"636","volume-title":"Proc. 40th Annual Allerton Conference on Communication, Control, and Computing","author":"A.Z. Broder","year":"2002","unstructured":"Broder, A.Z., Mitzenmacher, M.: Network applications of Bloom filters: A survey. In: Proc. 40th Annual Allerton Conference on Communication, Control, and Computing, pp. 636\u2013646. ACM Press, New York (2002)"},{"key":"32_CR5","unstructured":"Cain, J.A., Sanders, P., Wormald, N.C.: The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In: Proc. 18th ACM-SIAM SODA, pp. 469\u2013476 (2007)"},{"issue":"3","key":"32_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1017\/S0963548397003040","volume":"6","author":"N.J. Calkin","year":"1997","unstructured":"Calkin, N.J.: Dependent sets of constant weight binary vectors. Combinatorics, Probability and Computing\u00a06(3), 263\u2013271 (1997)","journal-title":"Combinatorics, Probability and Computing"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Carter, L., Floyd, R.W., Gill, J., Markowsky, G., Wegman, M.N.: Exact and approximate membership testers. In: Proc. 10th ACM STOC, pp. 59\u201365 (1978)","DOI":"10.1145\/800133.804332"},{"key":"32_CR8","unstructured":"Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: an efficient data structure for static support lookup tables. In: Proc. 15th ACM-SIAM SODA, pp. 30\u201339 (2004)"},{"issue":"2","key":"32_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.0.CO;2-1","volume":"16","author":"C. Cooper","year":"2001","unstructured":"Cooper, C.: On the rank of random matrices. Random Struct. Algorithms\u00a016(2), 209\u2013232 (2001)","journal-title":"Random Struct. Algorithms"},{"key":"32_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/978-3-540-45198-3_21","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Czumaj","year":"2003","unstructured":"Czumaj, A., Riley, C., Scheideler, C.: Perfectly Balanced Allocation. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 240\u2013251. Springer, Heidelberg (2003)"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-540-74871-7_2","volume-title":"Proc. 4th Int. Symp. on Stochastic Algorithms: Foundations and Applications (SAGA)","author":"M. Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M.: Design strategies for minimal perfect hash functions. In: Proc. 4th Int. Symp. on Stochastic Algorithms: Foundations and Applications (SAGA). LNCS, vol.\u00a04665, pp. 2\u201317. Springer, Heidelberg (2007)"},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership, Technical Report, arXiv:0803.3693v1 [cs.DS] (March 26, 2008)","DOI":"10.1007\/978-3-540-70575-8_32"},{"issue":"1\u20132","key":"32_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M. Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theoret. Comput. Sci.\u00a0380(1\u20132), 47\u201368 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"32_CR14","unstructured":"Fernholz, D., Ramachandran, V.: The k-orientability thresholds for G\n                    n,p. In: Proc. 18th ACM-SIAM SODA, pp. 459\u2013468 (2007)"},{"issue":"2","key":"32_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.G.: Space efficient hash tables with worst case constant access time. Theory Comput. Syst.\u00a038(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/3-540-44693-1_28","volume-title":"STACS 2001","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 317\u2013326. Springer, Heidelberg (2001)"},{"issue":"6","key":"32_CR17","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1093\/comjnl\/39.6.547","volume":"39","author":"B.S. Majewski","year":"1996","unstructured":"Majewski, B.S., Wormald, N.C., Havas, G., Czech, Z.J.: A family of perfect hashing methods. Computer J.\u00a039(6), 547\u2013554 (1996)","journal-title":"Computer J."},{"issue":"5","key":"32_CR18","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1109\/TNET.2002.803864","volume":"10","author":"M. Mitzenmacher","year":"2002","unstructured":"Mitzenmacher, M.: Compressed Bloom filters. IEEE\/ACM Transactions on Networking\u00a010(5), 604\u2013612 (2002)","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., P\u01cetra\u015fcu, M.: On dynamic range reporting in one dimension. In: Proc. 37th ACM STOC, pp. 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo Hashing. J. Algorithms\u00a051, 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"32_CR21","unstructured":"Panigrahy, R.: Efficient hashing with lookups in two memory accesses. In: Proc. 16th ACM-SIAM SODA, pp. 830\u2013839 (2005)"},{"key":"32_CR22","unstructured":"Porat, E.: An optimal Bloom filter replacement based on matrix solving, Technical Report, arXiv:0804.1845v1 [cs.DS] (April 11, 2008)"},{"issue":"6","key":"32_CR23","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0020-0190(94)00108-1","volume":"51","author":"S.S. Seiden","year":"1994","unstructured":"Seiden, S.S., Hirschberg, D.S.: Finding succinct ordered minimal perfect hash functions. Inf.\u00a0Process.\u00a0Lett.\u00a051(6), 283\u2013288 (1994)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Zukowski, M., Heman, S., Boncz, P.A.: Architecture-conscious hashing. In: Proc. Int. Workshop on Data Management on New Hardware (DaMoN), Chicago, 8 pages, Article No.\u00a06 (2006)","DOI":"10.1145\/1140402.1140410"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:27:11Z","timestamp":1714620431000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}