{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:50:48Z","timestamp":1743123048229,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":23,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_16","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:52Z","timestamp":1461269032000},"page":"90-94","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","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","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"1_CR1332","doi-asserted-by":"crossref","unstructured":"Alon N and Feige U (2009) On the power of two, three and four probes. In: Proceedings of SODA\u201909, New York, pp\u00a0346\u2013354","DOI":"10.1137\/1.9781611973068.39"},{"key":"1_CR1333","doi-asserted-by":"crossref","unstructured":"Brodnik A, Munro JI (1994) Membership in constant time and minimum space. In: Algorithms ESA\u201994: second annual European symposium, Utrecht. Lecture notes in computer science, vol 855, pp\u00a072\u201381. Final version: Membership in constant time and almost-minimum space. SIAM J Comput 28(5):1627\u20131640 (1999)","DOI":"10.1007\/BFb0049398"},{"issue":"6","key":"1_CR1334","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1137\/S0097539702405292","volume":"31","author":"H Buhrman","year":"2002","unstructured":"Buhrman H, Miltersen PB, Radhakrishnan J, Venkatesh S (2002) Are bitvectors optimal? SIAM J Comput 31(6):1723\u20131744","journal-title":"SIAM J Comput"},{"issue":"1","key":"1_CR1335","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/110834949","volume":"42","author":"V Chen","year":"2013","unstructured":"Chen V, Grigorescu E, de Wolf R (2013) Error-correcting data structures. SIAM J Comput 42(1):84\u2013111","journal-title":"SIAM J Comput"},{"issue":"3","key":"1_CR1336","first-page":"7","volume":"18","author":"AG Dyachkov","year":"1982","unstructured":"Dyachkov AG, Rykov VV (1982) Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii 18(3):7\u201313 [Russian]","journal-title":"Problemy Peredachi Informatsii"},{"key":"1_CR1337","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1145\/321892.321899","volume":"22","author":"P Elias","year":"1975","unstructured":"Elias P, Flower RA (1975) The complexity of some simple retrieval problems. J Assoc Comput Mach 22:367\u2013379","journal-title":"J Assoc Comput Mach"},{"key":"1_CR1338","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P Erd\u0151s","year":"1985","unstructured":"Erd\u0151s P, Frankl P, F\u00fcredi Z (1985) Families of finite sets in which no set is covered by the union of r others. Isr J Math 51:79\u201389","journal-title":"Isr J Math"},{"key":"1_CR1339","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0222001","volume":"22","author":"A Fiat","year":"1993","unstructured":"Fiat A, Naor M (1993) Implicit O(1) probe search. SIAM J Comput 22:1\u201310","journal-title":"SIAM J Comput"},{"key":"1_CR1340","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 JP, Siegel A (1992) Non-oblivious hashing. J Assoc Comput Mach 31:764\u2013782","journal-title":"J Assoc Comput Mach"},{"issue":"3","key":"1_CR1341","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman ML, Koml\u00f3s J, Szemer\u00e9di E (1984) Storing a sparse table with O(1) worst case access time. J Assoc Comput Mach 31(3):538\u2013544","journal-title":"J Assoc Comput Mach"},{"key":"1_CR1342","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 (1996) On r-cover-free families. J Comb Theory Ser A 73:172\u2013173","journal-title":"J Comb Theory Ser A"},{"key":"1_CR1343","doi-asserted-by":"crossref","unstructured":"Garg M, Radhakrishnan J (2015) Set membership with a few bit probes. In: Proceedings of SODA\u201915, San Diego, pp\u00a0776\u2013784","DOI":"10.1137\/1.9781611973730.53"},{"key":"1_CR1344","doi-asserted-by":"crossref","unstructured":"Katz J, Trevisan L (2000) On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of STOC\u201900, Portland, pp\u00a080\u201386","DOI":"10.1145\/335305.335315"},{"key":"1_CR1345","doi-asserted-by":"crossref","unstructured":"Lewenstein M, Munro JI, Nicholson PK, Raman V (2014) Improved explicit data structures in the bitprobe model. In: Proceedings of ESA\u201914, Wroclaw, pp\u00a0630\u2013641","DOI":"10.1007\/978-3-662-44777-2_52"},{"key":"1_CR1346","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"PB Miltersen","year":"1998","unstructured":"Miltersen PB, Nisan N, Safra S, Wigderson A (1998) On data structures and asymmetric communication complexity. J Comput Syst Sci 57:37\u201349","journal-title":"J Comput Syst Sci"},{"key":"1_CR1347","volume-title":"Perceptrons","author":"M Minsky","year":"1969","unstructured":"Minsky M, Papert S (1969) Perceptrons. MIT, Cambridge"},{"key":"1_CR1348","doi-asserted-by":"crossref","unstructured":"Pagh R (1999) Low redundancy in static dictionaries with O(1) lookup time. In: Proceedings of ICALP \u201999, Prague. Lecture notes in computer science, vol 1644, pp\u00a0595\u2013604","DOI":"10.1007\/3-540-48523-6_56"},{"key":"1_CR1349","doi-asserted-by":"crossref","unstructured":"Radhakrishnan J, Raman V, Rao SS (2001) Explicit deterministic constructions for membership in the bitprobe model. In: Proceedings of ESA\u201901, Aarhus, pp\u00a0290\u2013299","DOI":"10.1007\/3-540-44676-1_24"},{"key":"1_CR1350","doi-asserted-by":"crossref","unstructured":"Radhakrishnan J, Shah S, Shannigrahi S (2010) Data structures for storing small sets in the bitprobe model. In: Proceedings of ESA\u201910, Liverpool, pp\u00a0159\u2013170","DOI":"10.1007\/978-3-642-15781-3_14"},{"key":"1_CR1351","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/0097-3165(94)90067-1","volume":"66","author":"M Ruszink\u00f3","year":"1984","unstructured":"Ruszink\u00f3 M (1984) On the upper bound of the size of r-cover-free families. J Comb Theory Ser A 66:302\u2013310","journal-title":"J Comb Theory Ser A"},{"issue":"5","key":"1_CR1352","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 (2002) Explicit one-probe storing schemes using universal extractors. Inf Process Lett 83(5):267\u2013274","journal-title":"Inf Process Lett"},{"issue":"6","key":"1_CR1353","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1137\/090766619","volume":"41","author":"E Viola","year":"2012","unstructured":"Viola E (2012) Bit-probe lower bounds for succinct data structures. SIAM J Comput 41(6):1593\u20131604","journal-title":"SIAM J Comput"},{"issue":"3","key":"1_CR1354","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"ACC Yao","year":"1981","unstructured":"Yao ACC (1981) Should tables be sorted? J Assoc Comput Mach 28(3):615\u2013628","journal-title":"J Assoc Comput Mach"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T19:06:37Z","timestamp":1567796797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_16","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}