{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:41Z","timestamp":1759637681135},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_19","type":"book-chapter","created":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T21:20:34Z","timestamp":1376083234000},"page":"303-318","source":"Crossref","is-referenced-by-count":14,"title":["A Survey of Data Structures in the Bitprobe Model"],"prefix":"10.1007","author":[{"given":"Patrick K.","family":"Nicholson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/1.9781611973068.39","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009","author":"N. Alon","year":"2009","unstructured":"Alon, N., Feige, U.: On the power of two, three and four probes. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 346\u2013354. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"issue":"2","key":"19_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(84)90098-X","volume":"19","author":"H. Alt","year":"1984","unstructured":"Alt, H., Mehlhorn, K., Munro, J.I.: Partial match retrieval in implicit data structures. Inf. Process. Lett.\u00a019(2), 61\u201365 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"19_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":"19_CR4","unstructured":"Blue, R.: The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries. Master\u2019s thesis, University of Maryland (2009)"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0304-3975(88)90018-7","volume":"58","author":"A. Borodin","year":"1988","unstructured":"Borodin, A., Fich, F.E., Meyer auf der Heide, F., Upfal, E., Wigderson, A.: A tradeoff between search and update time for the implicit dictionary problem. Theor. Comput. Sci.\u00a058, 57\u201368 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-642-13731-0_22","volume-title":"Algorithm Theory - SWAT 2010","author":"P. Bose","year":"2010","unstructured":"Bose, P., Carmi, P., Jansens, D., Maheshwari, A., Morin, P., Smid, M.: Improved methods for generating quasi-Gray codes. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 224\u2013235. Springer, Heidelberg (2010)"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-20877-5_22","volume-title":"Theory and Applications of Models of Computation","author":"G.S. Brodal","year":"2011","unstructured":"Brodal, G.S., Greve, M., Pandey, V., Rao, S.S.: Integer representations towards efficient counting in the bit probe model. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol.\u00a06648, pp. 206\u2013217. Springer, Heidelberg (2011)"},{"issue":"1","key":"19_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0020-0190(00)00079-X","volume":"75","author":"G.S. Brodal","year":"2000","unstructured":"Brodal, G.S., Venkatesh, S.: Improved bounds for dictionary look-up with one error. Information Processing Letters\u00a075(1), 57\u201359 (2000)","journal-title":"Information Processing Letters"},{"issue":"4","key":"19_CR9","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1080\/15427951.2004.10129096","volume":"1","author":"A. Broder","year":"2004","unstructured":"Broder, A., Mitzenmacher, M.: Network applications of bloom filters: A survey. Internet Mathematics\u00a01(4), 485\u2013509 (2004)","journal-title":"Internet Mathematics"},{"issue":"5","key":"19_CR10","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and almost-minimum space. SIAM Journal on Computing\u00a028(5), 1627\u20131640 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"19_CR11","doi-asserted-by":"publisher","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 Journal on Computing\u00a031(6), 1723\u20131744 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR12","unstructured":"Clancy, M.J., Knuth, D.E.: A programming and problem-solving seminar. Tech. rep., Stanford, CA, USA (1977)"},{"issue":"1","key":"19_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0196-6774(03)00043-9","volume":"48","author":"E.D. Demaine","year":"2003","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A.: A linear lower bound on index size for text retrieval. Journal of Algorithms\u00a048(1), 2\u201315 (2003)","journal-title":"Journal of Algorithms"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Dodis, Y., P\u01cetra\u015fcu, M., Thorup, M.: Changing base without losing space. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 593\u2013602. ACM (2010)","DOI":"10.1145\/1806689.1806771"},{"issue":"3","key":"19_CR15","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. Journal of the ACM (JACM)\u00a022(3), 367\u2013379 (1975)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"19_CR16","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s00224-011-9357-0","volume":"50","author":"A. Elmasry","year":"2012","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Two skew-binary numeral systems and one application. Theory Comput. Syst.\u00a050(1), 185\u2013211 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1145\/256303.256309","volume":"44","author":"G.S. Frandsen","year":"1997","unstructured":"Frandsen, G.S., Miltersen, P.B., Skyum, S.: Dynamic word problems. J. ACM\u00a044(2), 257\u2013271 (1997)","journal-title":"J. ACM"},{"issue":"2","key":"19_CR18","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0207012","volume":"7","author":"M.L. Fredman","year":"1978","unstructured":"Fredman, M.L.: Observations on the complexity of generating quasi-Gray codes. SIAM Journal on Computing\u00a07(2), 134\u2013146 (1978)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"19_CR19","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 sparse table with 0(1) worst case access time. Journal of the ACM (JACM)\u00a031(3), 538\u2013544 (1984)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"19_CR20","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1145\/322290.322305","volume":"29","author":"M. Fredman","year":"1982","unstructured":"Fredman, M.: The complexity of maintaining an array and computing its partial sums. J. ACM\u00a029(1), 250\u2013260 (1982)","journal-title":"J. ACM"},{"issue":"3","key":"19_CR21","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.tcs.2007.02.047","volume":"379","author":"A. G\u00e1l","year":"2007","unstructured":"G\u00e1l, A., Miltersen, P.B.: The cell probe complexity of succinct data structures. Theor. Comput. Sci.\u00a0379(3), 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"19_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1541885.1541889","volume":"5","author":"Y. Giora","year":"2009","unstructured":"Giora, Y., Kaplan, H.: Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Transactions on Algorithms\u00a05(3), 28:1\u201328:51 (2009)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"19_CR23","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theoretical Computer Science\u00a0387(3), 348\u2013359 (2007)","journal-title":"Theoretical Computer Science"},{"key":"19_CR24","unstructured":"Golynski, A., Orlandi, A., Raman, R., Rao, S.S.: Optimal indexes for sparse bit vectors. Algorithmica, 1\u201319 (2011)"},{"key":"19_CR25","unstructured":"Gray, F.: Pulse code communications. U.S. Patent (2632058) (1953)"},{"key":"19_CR26","unstructured":"Jansens, D.: Improved Methods for Generating Quasi-Gray Codes. Master\u2019s thesis, School of Computer Science, Carleton University (April 2010)"},{"key":"19_CR27","volume-title":"Sorting and searching: The art of computer programming III","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: Sorting and searching: The art of computer programming III. Addison-Wesley, Reading (1973)"},{"key":"19_CR28","unstructured":"Knuth, D.E.: The Art of Computer Programming. Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming), vol.\u00a04. Addison-Wesley Professional (2005)"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Lewenstein, M., Munro, J.I., Nicholson, P.K., Raman, V.: Explicit data structures in the bitprobe model (submitted manuscript, 2013)","DOI":"10.1007\/978-3-662-44777-2_52"},{"key":"19_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/3-540-56503-5_65","volume-title":"STACS 93","author":"P.B. Miltersen","year":"1993","unstructured":"Miltersen, P.B.: The bit probe complexity measure revisited. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol.\u00a0665, pp. 662\u2013671. Springer, Heidelberg (1993), \n                  \n                    http:\/\/portal.acm.org\/citation.cfm?id=646509.694667"},{"key":"19_CR31","unstructured":"Minsky, M.L., Papert, S.: Perceptrons: An Introduction to Computational Geometry. The MIT Press (1969)"},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., Patrascu, M.: On dynamic range reporting in one dimension. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 104\u2013111. ACM (2005)","DOI":"10.1145\/1060590.1060606"},{"issue":"2","key":"19_CR33","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. Journal of Computer and System Sciences\u00a049(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"Okasaki, C.: Purely functional data structures. Cambridge University Press (1999)","DOI":"10.1017\/CBO9780511530104"},{"key":"19_CR35","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal bloom filter replacement. In: SODA, pp. 823\u2013829. SIAM (2005)"},{"issue":"2","key":"19_CR36","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing\u00a031(2), 353\u2013363 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR37","first-page":"425","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC 2001","author":"R. Pagh","year":"2001","unstructured":"Pagh, R.: On the cell probe complexity of membership and perfect hashing. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 425\u2013432. ACM, New York (2001)"},{"key":"19_CR38","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 305\u2013313. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.83"},{"issue":"1","key":"19_CR39","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.tcs.2007.02.058","volume":"380","author":"M. P\u01cetra\u015fcu","year":"2007","unstructured":"P\u01cetra\u015fcu, M., Tarni\u0163\u01ce, C.E.: On dynamic bit-probe complexity. Theoretical Computer Science\u00a0380(1), 127\u2013142 (2007)","journal-title":"Theoretical Computer Science"},{"key":"19_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-44676-1_24","volume-title":"Algorithms - ESA 2001","author":"J. Radhakrishnan","year":"2001","unstructured":"Radhakrishnan, J., Raman, V., Rao, S.S.: Explicit deterministic constructions for membership in the bitprobe model. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 290\u2013299. Springer, Heidelberg (2001)"},{"key":"19_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-15781-3_14","volume-title":"Algorithms \u2013 ESA 2010","author":"J. Radhakrishnan","year":"2010","unstructured":"Radhakrishnan, J., Shah, S., Shannigrahi, S.: Data structures for storing small sets in the bitprobe model. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol.\u00a06347, pp. 159\u2013170. Springer, Heidelberg (2010)"},{"key":"19_CR42","unstructured":"Rahman, M.Z.: Data Structuring Problems in the Bit Probe Model. Master\u2019s thesis, University of Waterloo (2007)"},{"issue":"1","key":"19_CR43","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s00453-008-9247-2","volume":"56","author":"M.Z. Rahman","year":"2010","unstructured":"Rahman, M.Z., Munro, J.I.: Integer representation and counting in the bit probe model. Algorithmica\u00a056(1), 105\u2013127 (2010)","journal-title":"Algorithmica"},{"key":"19_CR44","unstructured":"Rao, S.S.: Succinct Data Structures. Ph.D. thesis, Institute of Mathematical Sciences (2001)"},{"key":"19_CR45","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S0036144595295272","volume":"39","author":"C. Savage","year":"1996","unstructured":"Savage, C.: A survey of combinatorial Gray codes. SIAM Review\u00a039, 605\u2013629 (1996)","journal-title":"SIAM Review"},{"issue":"5","key":"19_CR46","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.: Storing information with extractors. Information Processing Letters\u00a083(5), 267\u2013274 (2002)","journal-title":"Information Processing Letters"},{"issue":"278","key":"19_CR47","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1090\/S0025-5718-2011-02542-1","volume":"81","author":"T. Tao","year":"2012","unstructured":"Tao, T., Croot III., E., Helfgott, H.: Deterministic methods to find primes. Mathematics of Computation\u00a081(278), 1233\u20131246 (2012)","journal-title":"Mathematics of Computation"},{"issue":"6","key":"19_CR48","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1137\/090766619","volume":"41","author":"E. Viola","year":"2012","unstructured":"Viola, E.: Bit-probe lower bounds for succinct data structures. SIAM Journal on Computing\u00a041(6), 1593\u20131604 (2012)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"19_CR49","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM\u00a021(4), 309\u2013315 (1978)","journal-title":"Commun. ACM"},{"issue":"3","key":"19_CR50","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"Yao, A.C.: Should tables be sorted? J. ACM\u00a028(3), 615\u2013628 (1981)","journal-title":"ACM"},{"issue":"1","key":"19_CR51","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1006\/jagm.1997.0875","volume":"25","author":"A.C. Yao","year":"1997","unstructured":"Yao, A.C., Yao, F.F.: Dictionary look-up with one error. Journal of Algorithms\u00a025(1), 194\u2013202 (1997)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T10:49:56Z","timestamp":1558003796000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}