{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T03:18:43Z","timestamp":1775618323033,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540404934","type":"print"},{"value":"9783540450610","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_28","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"332-344","source":"Crossref","is-referenced-by-count":9,"title":["The Cell Probe Complexity of Succinct Data Structures"],"prefix":"10.1007","author":[{"given":"Anna","family":"G\u00e1l","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF02126797","volume":"8","author":"M. Ajtai","year":"1988","unstructured":"M. Ajtai. A lower bound for finding predecessors in Yao\u2019s cell probe model. Combinatorica, 8:235\u2013247, 1988.","journal-title":"Combinatorica"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"N. Alon, O. Goldreich, J. H\u00e5stad, R. Peralta: Simple constructions of almost kwise independent random variables. Random Structures and Algorithms 3 (1992), 289\u2013304.","journal-title":"Random Structures and Algorithms"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"O. Barkol and Y. Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model. In Proc. 32th Annual ACM Symposium on Theory of Computing (STOC\u201900), pages 388\u2013396.","DOI":"10.1145\/335305.335350"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"A. Borodin, R. Ostrovsky, Y. Rabani, Lower bounds for high dimensional nearest neighbor search and related problems. In Proc. 31th Annual ACM Symposium on Theory of Computing (STOC\u201999), pages 312\u2013321.","DOI":"10.1145\/301250.301330"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"A. Brodnik and J.I. Munro. Membership in constant time and almost-minim um space. SIAM Journal on Computing, 28:1627\u20131640, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"H. Buhrman, P.B. Miltersen, J. Radhakrishnan, S. Venkatesh. Are bitvectors optimal? In Proc. 32th Annual ACM Symposium on Theory of Computing (STOC\u201900), pages 449\u2013458.","DOI":"10.1145\/335305.335357"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, B. Chazelle, B. Gum, and A. Lvov. A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming Cube. In Proc. 31th Annual ACM Symposium on Theory of Computing (STOC\u201999), pages 305\u2013311.","DOI":"10.1145\/301250.301325"},{"key":"28_CR8","unstructured":"E.D. Demaine and A. Lopez-Ortiz. A Linear Lower Boundon Index Size for Text Retrieval. In Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901), pages 289\u2013294."},{"key":"28_CR9","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1145\/321892.321899","volume":"22","author":"P. Elias","year":"1975","unstructured":"P. Elias and R. A. Flower. The complexity of some simple retrieval problems. Journal of the Association for Computing Machinery, 22:367\u2013379, 1975.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and R. Rado. Intersection theorems for systems of sets. Journal of London Mathematical Society 35 (1960), pages 85\u201390.","journal-title":"Journal of London Mathematical Society"},{"key":"28_CR11","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. Journal of the Association for Computing Machinery, 31:538\u2013544, 1984.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"R. Grossi, J.S. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In Proc. 32th Annual ACM Symp. on Theory of Computing (STOC\u201900), pages 397\u2013406.","DOI":"10.1137\/S0097539702402354"},{"key":"28_CR13","unstructured":"R. Grossi, A. Gupta, and J.S. Vitter. High-Order Entropy-Compressed Text Indexes. In Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA\u201903), pages 841\u2013850."},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(73)90098-8","volume":"6","author":"D. J. Kleitman","year":"1973","unstructured":"D. J. Kleitman and J. Spencer: Families of k-independent sets. Discrete Math. 6 (1973), pp. 255\u2013262.","journal-title":"Discrete Math"},{"key":"28_CR15","volume-title":"The Art of Computer Programming, Vol. II: Seminumerical Algorithms","author":"D.E. Knuth","year":"1980","unstructured":"D.E. Knuth, The Art of Computer Programming, Vol. II: Seminumerical Algorithms (Addison-Wesley, Reading, MA, 2nd ed., 1980).","edition":"2nd ed."},{"key":"28_CR16","volume-title":"The theory of error correcting codes","author":"F. J. MacWilliams","year":"1981","unstructured":"F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier\/North-Holland, Amsterdam, 1981."},{"key":"28_CR17","unstructured":"U. Manber, S. Wu. GLIMPSE \u2014 A Tool to Search Through Entire Filesystems. White Paper. Available at http:\/\/glimpse.cs.arizona.edu\/."},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"P.B. Miltersen. The bitprobe complexity measure revisited. In 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201993), pages 662\u2013671, 1993.","DOI":"10.1007\/3-540-56503-5_65"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0304-3975(95)80018-2","volume":"143","author":"P.B. Miltersen","year":"1995","unstructured":"P.B. Miltersen, On the cell probe complexity of polynomial evaluation, Theoretical Computer Science, 143:167\u2013174, 1995.","journal-title":"Theoretical Computer Science"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P.B. Miltersen","year":"1998","unstructured":"P.B. Miltersen, N. Nisan, S. Safra, and A. Wigderson: On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, 57:37\u201349, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR21","volume-title":"Perceptrons","author":"M. Minsky","year":"1969","unstructured":"M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, Mass., 1969."},{"issue":"4","key":"28_CR22","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"J. Naor and M. Naor: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., Vol. 22, No. 4, (1993), pp. 838\u2013856.","journal-title":"SIAM J. Comput."},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"M. Naor, L. Schulman, A. Srinivasan: Splitters and near optimal derandomization. In Proc. of 36th IEEE FOCS, (1995), pp. 182\u2013191.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1137\/S0097539795282444","volume":"28","author":"N. Nisan","year":"1999","unstructured":"N. Nisan, S. Rudich, and M. Saks. Products and Help Bits in Decision Trees, SIAM J. Comput. 28:1035\u20131050, 1999.","journal-title":"SIAM J. Comput."},{"key":"28_CR25","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/3-540-48523-6_56","volume":"1644","author":"R. Pagh","year":"1999","unstructured":"R. Pagh. Low redundancy in static dictionaries with O(1) lookup time. In International Colloquium on Automata Languages and Programming (ICALP\u201999), Lecture Notes in Computer Science, Volume 1644, pages 595\u2013604, 1999.","journal-title":"International Colloquium on Automata Languages and Programming (ICALP\u201999), Lecture Notes in Computer Science"},{"key":"28_CR26","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1109\/18.6031","volume":"34","author":"G. Seroussi","year":"1988","unstructured":"G. Seroussi and N. Bshouty: Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inform. Theory, 34 (1988), pp. 513\u2013522.","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T06:28:29Z","timestamp":1683959309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}