2025/04/25 by Alina Ene, Alessandro Epasto, Ene, Alina +10
Computer Science · Decision Sciences · #Complexity and Algorithms in Graphs #Data Quality and Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2504.18394
openalex publication_date 2025/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the maximum coverage problem we are given d subsets from a universe [n], and the goal is to output k subsets such that their union covers the largest possible number of distinct items. We present the first algorithm for maximum coverage in the turnstile streaming model, where updates which insert or delete an item from a subset come one-by-one. Notably our algorithm only uses polylog n update time. We also present turnstile streaming algorithms for targeted and general fingerprinting for risk management where the goal is to determine which features pose the greatest re-identification risk in a dataset. As part of our work, we give a result of independent interest: an algorithm to estimate the complement of the pth frequency moment of a vector for p ≥ 2. Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to 210x over prior work.