Research map / Learning theory and algorithms / Prediction and decision losses

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Approximate nearest neighbor indexing · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first turnstile streaming algorithm for maximum coverage with polylog n update time, extends it to targeted and general fingerprinting, and introduces a linear sketch for n^p - F_p (p>=2).

Problem

Maximum coverage and fingerprinting-based re-identification risk measurement over dynamic datasets with insertions and deletions in the turnstile streaming model.

Approach

Adapts the insertion-only subsampling sketch of Bateni et al. into a linear sketch using L0 sketches, CountSketch and multi-level subsampling so that item-subset insertions and deletions are supported with polylog update time; reduces targeted fingerprinting to maximum coverage and general fingerprinting to a submodular framework with a new sketch for n^p - F_p.

Key results

• Targeted fingerprinting speedup of up to 49x over prior implementation with high comparative accuracy.
• General fingerprinting speedup of up to 210x while retaining high accuracy.
• Turnstile maximum coverage sketch uses tilde-O(d/eps^3) space with tilde-O(1) update time and (1-1/e-eps) approximation w.p. 1-1/d.

Measured effects reported in the paper

Limitations

• General fingerprinting space scales as d k^3/eps^2 due to setting gamma = eps/k.
• Results rely on linear sketches and probabilistic guarantees that hold with high probability only.

Experimental setup

Datasets: Adult

Benchmarks: Adult

Metrics: runtime speedup approximation accuracy

Baselines: Gulyás, Ács, and Castelluccia fingerprinting implementation greedy maximum coverage

Builds on: Bateni et al. maximum coverage sketch CountSketch Horel and Singer submodular analysis Nemhauser-Wolsey-Fisher greedy

Closest papers by meaning

• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.85)
• Turnstile $\ell_p$ leverage score sampling with applications (ICML 2024 · similarity 0.84)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization (ICML 2024 · similarity 0.82)
• Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.82)
• Scalable Fingerprinting of Large Language Models (NeurIPS 2025 · similarity 0.82)
• Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.82)