Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915275656396800 |
|---|---|
| author | Ene, Alina Epasto, Alessandro Mirrokni, Vahab Nguyen, Hoai-An Nguyen, Huy L. Woodruff, David P. Zhong, Peilin |
| author_facet | Ene, Alina Epasto, Alessandro Mirrokni, Vahab Nguyen, Hoai-An Nguyen, Huy L. Woodruff, David P. Zhong, Peilin |
| contents | 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 $poly\log 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 $p^{\text{th}}$ frequency moment of a vector for $p \geq 2$. Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to $210$x over prior work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18394 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures Ene, Alina Epasto, Alessandro Mirrokni, Vahab Nguyen, Hoai-An Nguyen, Huy L. Woodruff, David P. Zhong, Peilin Data Structures and Algorithms 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 $poly\log 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 $p^{\text{th}}$ frequency moment of a vector for $p \geq 2$. Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to $210$x over prior work. |
| title | Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.18394 |