{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T16:38:16Z","timestamp":1771259896585,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_65","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"730-741","source":"Crossref","is-referenced-by-count":4,"title":["Storing a Compressed Function with Constant Time Access"],"prefix":"10.1007","author":[{"given":"J\u00f3hannes B.","family":"Hreinsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morten","family":"Kr\u00f8yer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"65_CR1","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009). ACM Press, New York (2009)"},{"key":"65_CR2","first-page":"132","volume-title":"ALENEX","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Theory and practise of monotone minimal perfect hashing. In: Finocchi, I., Hershberger, J. (eds.) ALENEX, pp. 132\u2013144. SIAM, Philadelphia (2009)"},{"issue":"7","key":"65_CR3","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. Communications of the ACM\u00a013(7), 422\u2013426 (1970)","journal-title":"Communications of the ACM"},{"key":"65_CR4","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)"},{"issue":"3","key":"65_CR5","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 & Computing\u00a06(3), 263\u2013271 (1997)","journal-title":"Combinatorics, Probability & Computing"},{"key":"65_CR6","first-page":"59","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978)","author":"L. Carter","year":"1978","unstructured":"Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Exact and approximate membership testers. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 59\u201365. ACM Press, New York (1978)"},{"key":"65_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-540-87744-8_22","volume-title":"Algorithms - ESA 2008","author":"D. Charles","year":"2008","unstructured":"Charles, D., Chellapilla, K.: Bloomier filters: A second look. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 259\u2013270. Springer, Heidelberg (2008)"},{"key":"65_CR8","first-page":"30","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)","author":"B. Chazelle","year":"2004","unstructured":"Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: An efficient data structure for static support lookup tables. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 30\u201339. ACM Press, New York (2004)"},{"key":"65_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership (Extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 385\u2013396. Springer, Heidelberg (2008)"},{"issue":"6","key":"65_CR10","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1109\/TIT.1978.1055959","volume":"24","author":"R. Gallager","year":"1978","unstructured":"Gallager, R.: Variations on a theme by Huffman. IEEE Transactions on Information Theory\u00a024(6), 668\u2013674 (1978)","journal-title":"IEEE Transactions on Information Theory"},{"key":"65_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"STACS 98","author":"T. Hagerup","year":"1998","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 366\u2013398. Springer, Heidelberg (1998)"},{"key":"65_CR12","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":"9","key":"65_CR13","first-page":"1098","volume":"40","author":"D.A. Huffman","year":"1952","unstructured":"Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers\u00a040(9), 1098\u20131101 (1952)","journal-title":"Proceedings of the Institute of Radio Engineers"},{"issue":"3","key":"65_CR14","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1145\/79147.79150","volume":"37","author":"L.L. Larmore","year":"1990","unstructured":"Larmore, L.L., Hirschberg, D.S.: A fast algorithm for optimal length-limited Huffman codes. Journal of the ACM\u00a037(3), 464\u2013473 (1990)","journal-title":"Journal of the ACM"},{"issue":"4","key":"65_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s00453-001-0060-4","volume":"31","author":"R.L. Milidi\u00fa","year":"2001","unstructured":"Milidi\u00fa, R.L., Laber, E.S.: Bounding the inefficiency of length-restricted prefix codes. Algorithmica\u00a031(4), 513\u2013529 (2001)","journal-title":"Algorithmica"},{"key":"65_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"65_CR17","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proceedings of the 49th Annual Symposium on Foundations of Computer Science (FOCS 2008), pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"65_CR18","unstructured":"Porat, E.: An optimal Bloom filter replacement based on matrix solving. CoRR, abs\/0804.1845 (2008)"},{"issue":"5","key":"65_CR19","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J.P. Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput.\u00a019(5), 775\u2013786 (1990)","journal-title":"SIAM J. Comput."},{"key":"65_CR20","volume-title":"Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)","author":"D. Talbot","year":"2008","unstructured":"Talbot, D., Talbot, J.M.: Bloom maps. In: Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). IEEE, Los Alamitos (2008)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_65","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:22:07Z","timestamp":1558524127000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}