Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures

Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong · 2025

Read Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures by Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18394.txt.

Introduction

Alina Ene and co-authors present streaming algorithms in a 2025 paper. The maximum coverage problem asks which few sets cover the most items. In a turnstile stream, items enter and leave sets one update at a time, and memory is tight. Their algorithm is the first for coverage in this harsh model, with very fast updates.

The team also builds stream tools for fingerprinting, which flags which traits most risk re-identifying people in a data set. A side result estimates a missing frequency moment for large vectors. Tests showed speedups up to two hundred ten times over prior fingerprinting work. Readers get privacy risk tools that run at stream speed.

Catalog record

CREATORAlina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-18394

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong Abstract In the maximum coverage problem we are given d d subsets from a universe [ n ] [n] , and the goal is to output k 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 \mathrm{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 p th p^{\text{th}} frequency moment of a vector for p ≥ 2 p\geq 2 . Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to 210 210 x over prior work. 1 Introduction Maximum coverage is a classic NP-hard problem with applications including information retrieval [ ABB+15 ] , influence maximization [ KKT15 ] , and sensor placement [ KG07 ] . Given d subsets of a universe containing n items and a cardinality constraint k\geq 0 , the goal is to output the k subsets whose union covers the largest possible number of distinct items. Feige demonstrated that a simple greedy algorithm — running in O(knd) time and using O(nd) space — achieves a tight 1-1/e relative approximation (assuming P \neq NP) [ Fei98 ] . The algorithm iterates for k rounds and selects the subset that maximizes the marginal gain at each step. However, its polynomial time and space complexity make it impractical for large-scale datasets. Our goal therefore is to develop more efficient algorithms for maximum coverage. To this end, we present the first one-pass turnstile streaming algorithm for maximum coverage. In the turnstile streaming model, updates come one-by-one in a stream. Each update inserts or deletes an item from a subset. The goal is to process each update efficiently while only maintaining sublinear space and then output the answer at the end of the stream. Our algorithm uses sublinear space and notably only \mathrm{polylog}n update time to output a near-tight (1-1/e-\varepsilon) approximation to the answer. Our algorithm is one-pass, meaning it takes only one pass over the stream of updates. Our algorithm offers efficient time complexity even with direct access to the full input. The input can be provided as a sequence of updates, and the total runtime is near-linear in the number of items across the input subsets. In addition, allowing arbitrary deletions of items from subsets is critical for numerous applications, including the following extension to fingerprinting for dataset risk management. We also develop turnstile streaming algorithms for targeted and general fingerprinting. The input consists of n users and d features, where each user has a value assigned for each feature. In targeted fingerprinting, the goal is to select k features that minimize the number of users who share identical values with a given target user u\in[n] at these features. In general fingerprinting, the goal is to select k features that minimize the number of user pairs with matching values across those features. Here an update in the stream changes the value of a user at a feature. Our fingerprinting algorithms fit into the broader privacy attack literature [ SDG23 , CDP+19 , ZWZL23 ] and is an extension of the work of Chia, Desfontaines, Perera, Simmons-Marengo, Li, Day, Wang, and Guevara [ CDP+19 ] in privacy auditing and risk measurement. Fingerprinting, which identifies users based on unique attribute combinations in a dataset, poses a significant privacy risk. Our algorithms mitigate this risk by identifying the k features most likely to allow adversaries to successfully fingerprint users. Previous work, except for that of Gulyás, Ács, and Castelluccia [ GÁC16 ] (whose algorithms we improve), has only measured the risk of entire datasets or fixed sets of features. In contrast, our time and space efficient algorithms are suited for real-time monitoring of the re-identification risks even as a dataset evolves. Additionally, targeted fingerprinting is a form of frequency estimation with potential applications in discovering heavy hitters [ BDW16 , ZKM+20 ] . Our algorithms are all linear sketches, powerful structures that compress the input matrix while time efficiently handling insertions and deletions. Unlike algorithms designed for specific models, linear sketches are applicable across a wide range of settings. Besides directly implying turnstile streaming algorithms, they are well-suited for distributed contexts. One popular application for linear sketches is in the coordinator model where there are k distributed machines and one coordinator. The input is split into pieces, and each machine gets a piece. They can only communicate with the coordinator (and want to minimize communication), and the goal is to get a joint solution. Another application is in parallel computation where there are k distributed machines who can communicate to compute a joint solution. The goal is to again minimize the amount of communication. 1.1 Related Work There is an extensive body of work on the maximum coverage problem, and we only attempt to give an overview of the most relevant works. In the following, an x -relative approximation means that the number of distinct items covered by the k subsets outputted by the algorithm is at least x\cdot\mathbf{OPT} , where \mathbf{OPT} is the number of distinct items covered by the optimal solution. \tilde{O}(\cdot) notation is used to suppress poly-logarithmic factors in its argument. McGregor and Vu [ MV19 ] provide a one-pass streaming algorithm 1 1 1 See Section 2.2 about the streaming model. that outputs a (1-1/e-\varepsilon) - relative approximation for \varepsilon\in(0,1) in \tilde{O}(d/\varepsilon^{2}) space. They consider the insertion-only set-arrival streaming model where each update reveals a subset and all the items it covers, and deletions are not supported. Bateni, Esfandiari, and Mirrokni [ BEM17 ] give a one-pass (1-1/e-\varepsilon) relative approximation algorithm that uses \tilde{O}(d/\varepsilon^{3}) memory. They consider the insertion-only streaming model where deletions are not supported. They specifically provide an algorithm that carefully samples a number of item-subset relationships and then show that any (\alpha) -relative approximation on this smaller subsampled universe achieves a (\alpha-\varepsilon) -relative approximation for the original input. We use their sketch as a starting point. There has also been work that achieves different approximation factors [ SG09 , MTV21 ] , in random-arrival streams [ WCW23 , CMW24 ] , with multiple passes [ CMW24 ] , and in more general submodular maximization in the insertion-only set-arrival streaming model [ BMKK14 , KMZ+19 ] . In contrast to all of the above, our algorithm allows arbitrary insertions or deletions of items from subsets. Note that there are more lines of work in the model where each update is the insertion or deletion of an entire subset (rather than items from subsets which we consider) than listed above. There has also been work on maximum coverage and submodular maximization in the dynamic model [ Mon20 , CP22 , LMN+20 ]

Read the complete text