{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:07:34Z","timestamp":1743084454386,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":16,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_16","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:37:51Z","timestamp":1214505471000},"page":"43-45","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Dictionaries"],"prefix":"10.1007","author":[{"given":"Venkatesh","family":"Srinivasan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1_16","doi-asserted-by":"crossref","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and minimum space. In: Lecture Notes in Computer Science, vol.\u00a0855, pp.\u00a072\u201381, Springer, Berlin (1994). Final version: Membership in Constant Time and Almost\u2010Minimum Space. SIAM J. Comput. 28(5), 1627\u20131640 (1999)","DOI":"10.1137\/S0097539795294165"},{"issue":"6","key":"16_CR2_16","doi-asserted-by":"crossref","first-page":"1723","DOI":"10.1137\/S0097539702405292","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., Miltersen, P.B., Radhakrishnan, J., Venkatesh, S.: Are bitvectors optimal? SIAM J. Comput. 31(6), 1723\u20131744 (2002)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR3_16","first-page":"7","volume":"18","author":"A.G. Dyachkov","year":"1982","unstructured":"Dyachkov, A.G., Rykov, V.V.: Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii 18(3), 7\u201313 (1982)","journal-title":"Problemy Peredachi Informatsii"},{"key":"16_CR4_16","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1145\/321892.321899","volume":"22","author":"P. Elias","year":"1975","unstructured":"Elias, P., Flower, R.A.: The complexity of some simple retrieval problems. J.\u00a0Assoc. Comput. Mach. 22, 367\u2013379 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR5_16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P. Erd\u00f6s","year":"1985","unstructured":"Erd\u00f6s, P., Frankl, P., F\u00fcredi, Z.: Families of finite sets in which no set is covered by the union of r others. Isr. J. Math. 51, 79\u201389 (1985)","journal-title":"Isr. J. Math."},{"key":"16_CR6_16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0222001","volume":"22","author":"A. Fiat","year":"1993","unstructured":"Fiat, A., Naor, M.: Implicit O(1) probe search. SIAM J. Comput. 22, 1\u201310 (1993)","journal-title":"SIAM J. Comput."},{"key":"16_CR7_16","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1145\/146585.146591","volume":"31","author":"A. Fiat","year":"1992","unstructured":"Fiat, A., Naor, M., Schmidt, J.P., Siegel, A.: Non\u2010oblivious hashing. J.\u00a0Assoc. Comput. Mach. 31, 764\u2013782 (1992)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"16_CR8_16","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a\u00a0sparse table with $$ { {O(1)} } $$ worst case access time. J.\u00a0Assoc. Comput. Mach. 31(3), 538\u2013544 (1984)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR9_16","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1006\/jcta.1996.0012","volume":"73","author":"Z. F\u00fcredi","year":"1996","unstructured":"F\u00fcredi, Z.: On r-cover-free families. J.\u00a0Comb. Theory, Series A 73, 172\u2013173 (1996)","journal-title":"J. Comb. Theory, Series A"},{"key":"16_CR10_16","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error\u2010correcting codes. In: Proceedings of STOC'00, pp.\u00a080\u201386"},{"key":"16_CR11_16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P.B. Miltersen","year":"1998","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J.\u00a0Comput. Syst. Sci. 57, 37\u201349 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR12_16","volume-title":"Perceptrons","author":"M. Minsky","year":"1969","unstructured":"Minsky, M., Papert, S.: Perceptrons. MIT Press, Cambridge (1969)"},{"key":"16_CR13_16","first-page":"595","volume-title":"Proceedings of ICALP '99. LNCS, vol. 1644","author":"R. Pagh","year":"1999","unstructured":"Pagh, R.: Low redundancy in static dictionaries with O(1) lookup time. In: Proceedings of ICALP '99. LNCS, vol.\u00a01644, pp.\u00a0595\u2013604. Springer, Berlin (1999)"},{"key":"16_CR14_16","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/0097-3165(94)90067-1","volume":"66","author":"M Ruszink\u00f3","year":"1984","unstructured":"Ruszink\u00f3, M. On the upper bound of the size of r-cover-free families. J.\u00a0Comb. Theory, Ser. A 66, 302\u2013310 (1984)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"5","key":"16_CR15_16","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S0020-0190(02)00206-5","volume":"83","author":"A. Ta-Shma","year":"2002","unstructured":"Ta-Shma, A.: Explicit one-probe storing schemes using universal extractors. Inf. Proc. Lett. 83(5), 267\u2013274 (2002)","journal-title":"Inf. Proc. Lett."},{"issue":"3","key":"16_CR16_16","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C.C. Yao","year":"1981","unstructured":"Yao, A.C.C.: Should tables be sorted? J. Assoc. Comput. Mach. 28(3), 615\u2013628 (1981)","journal-title":"Assoc. Comput. Mach."}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:00:25Z","timestamp":1662170425000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_16"}},"subtitle":["2002; Buhrman, Miltersen, Radhakrishnan, Venkatesh"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_16","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}