{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:52Z","timestamp":1787337472774,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We study the dynamic membership (or dynamic dictionary) problem, which is one of the most fundamental problems in data structures. We study the problem in the external memory model with cell size $b$ bits and cache size $m$ bits. We prove that if the amortized cost of updates is at most $0.9$ (or any other constant $&lt;1$), then the query cost must be $\\Omega(\\log_{b \\log n} (n\/m))$, where $n$ is the number of elements in the dictionary. In contrast, when the update time is allowed to be $1+o(1)$, then a bit vector or hash table gives query time $O(1)$. Thus, this is a threshold phenomenon for data structures. This lower bound answers a folklore conjecture of the external memory community. Since almost any data structure task can solve membership, our lower bound implies a dichotomy between two alternatives: (i) make the amortized update time at least $1$ (so the data structure does not buffer, and we lose one of the main potential advantages of the cache), or (ii) make the query time at least roughly logarithmic in $n$. Our result holds even when the updates and queries are chosen uniformly at random and there are no deletions; it holds for randomized data structures, holds when the universe size is $O(n)$, and does not make any restrictive assumptions such as indivisibility. All of the lower bounds we prove hold regardless of the space consumption of the data structure, while the upper bounds need only linear space. The lower bound has some striking implications for external memory data structures. It shows that the query complexities of many problems, such as one-dimensional range counting, predecessor, rank-select, and many others, are all the same in the regime where the amortized update time is less than $1$, as long as the cell size is large enough ($b=\\mathrm{polylog}(n)$ suffices). The proof of our lower bound is based on a new combinatorial lemma called the lemma of surprising intersections (LOSI), which allows us to use a proof methodology where we first analyze the intersection structure of the positive queries by using encoding arguments, and then use statistical arguments to deduce properties of the intersection structure of all queries, even the negative ones. In most other data structure arguments that we know, it is difficult to argue anything about the negative queries. Therefore we believe that the LOSI and this proof methodology might find future uses for other problems.<\/jats:p>","DOI":"10.1137\/110842211","type":"journal-article","created":{"date-parts":[[2013,1,29]],"date-time":"2013-01-29T12:52:05Z","timestamp":1359463925000},"page":"212-229","source":"Crossref","is-referenced-by-count":9,"title":["The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model"],"prefix":"10.1137","volume":"42","author":[{"given":"Elad","family":"Verbin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,1,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"atypb2","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 2004."},{"key":"atypb3","first-page":"313","author":"Arge L.","year":"2002","journal-title":"The Netherlands"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"atypb6","first-page":"546","author":"Brodal G. S.","year":"2003","journal-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.69"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.48"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9155-x"},{"key":"atypb12","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming, Volume3:Sorting and Searching\n                      , Addison-Wesley, Reading, MA, 1998."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/319758.319763"},{"key":"atypb14","first-page":"212","author":"Litwin W.","year":"1980","journal-title":"Proceedings of the International Conference on Very Large Databases"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, S. N\u00e4her, and M. Rauch,\n                      On the complexity of a game related to the dictionary problem\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 546-548.","DOI":"10.1109\/SFCS.1989.63532"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"atypb17","first-page":"14","author":"Pagh R.","year":"2003","journal-title":"Berlin"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"R. Pagh,\n                      On the cell probe complexity of membership and perfect hashing\n                      , in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 425-432.","DOI":"10.1145\/380752.380836"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu and M. Thorup,\n                      Time-space trade-offs for predecessor search\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 232-240.","DOI":"10.1145\/1132516.1132551"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.11"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.016"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"R. Sundar,\n                      A lower bound for the dictionary problem under a hashing model\n                      , in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 612-621.","DOI":"10.1109\/SFCS.1991.185427"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"J. S. Vitter,\n                      Algorithms and Data Structures for External Memory\n                      , Now Publishers, Hanover, MA, 2008.","DOI":"10.1561\/0400000014"},{"key":"atypb25","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/1583991.1584055","author":"Wei Z.","year":"2009","journal-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      Probabilistic computations: Towards a united measure of complexity\n                      , in Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science, 1977, pp. 222-227.","DOI":"10.1109\/SFCS.1977.24"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.12"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110842211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:19Z","timestamp":1787335939000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110842211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110842211"],"URL":"https:\/\/doi.org\/10.1137\/110842211","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}