We study differentially-private statistics in the fully dynamic continual observation model, where many updates can arrive at each time step and updates to a stream can involve both insertions and deletions of an item. Earlier work (e.g., Jain et al., NeurIPS 2023 for counting distinct elements; Raskhodnikova the key technical challenge is arguing that one can use state-of-the-art factorizations for sensitivity vector sets with the properties we isolate. In particular, we show that for approximate DP, the celebrated square-root factorization of the counting matrix (Henzinger et al., SODA 2023; Fichtenberger et al., ICML 2023) can be employed to give concrete improvements in accuracy over past work based on the binary tree mechanism. We also give a tight analysis of b -ary tree mechanisms with subtraction under these sensitivity patterns, including a polytime routine for computing the ℓ p sensitivity, yielding time and space efficient algorithms for both pure and approximate DP. Empirically and analytically, we demonstrate that our improved error bounds offer a substantial improvement in accuracy for cardinality estimation problems over a large range of parameters.
Andersson et al. (Tue,) studied this question.