2026-07-20T11:16:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4989 2024-03-06T10:35:40Z ddc:004 open_access

On The I/O Complexity of Dynamic Distinct Counting Hu, Xiaocheng Tao, Yufei Yang, Yi Zhang, Shengyu Zhou, Shuigeng distinct counting lower bound external memory In dynamic distinct counting, we want to maintain a multi-set S of integers under insertions to answer efficiently the query: how many distinct elements are there in S? In external memory, the problem admits two standard solutions. The first one maintains $S$ in a hash structure, so that the distinct count can be incrementally updated after each insertion using O(1) expected I/Os. A query is answered for free. The second one stores S in a linked list, and thus supports an insertion in O(1/B) amortized I/Os. A query can be answered in O(N/B log_{M/B} (N/B)) I/Os by sorting, where N=|S|, B is the block size, and M is the memory size. In this paper, we show that the above two naive solutions are already optimal within a polylog factor. Specifically, for any Las Vegas structure using N^{O(1)} blocks, if its expected amortized insertion cost is o(1/log B}), then it must incur Omega(N/(B log B)) expected I/Os answering a query in the worst case, under the (realistic) condition that N is a polynomial of B. This means that the problem is repugnant to update buffering: the query cost jumps from 0 dramatically to almost linearity as soon as the insertion cost drops slightly below Omega(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaocheng Hu and Yufei Tao and Yi Yang and Shengyu Zhang and Shuigeng Zhou 2015 Is Part Of LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2015.265 urn:nbn:de:0030-drops-49895 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.265 eng https://creativecommons.org/licenses/by/3.0/legalcode