Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Authors: Alina Ene
Alessandro Epasto
Vahab Mirrokni
Hoai-An Nguyen
Huy Nguyen
David Woodruff
Peilin Zhong
Venue: ICML 2025 poster (2025)
Keywords: maximum coverage
linear sketches
turnstile streams
algorithms
Primary area: theory->optimization

Abstract: 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.

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Alina Ene
Alessandro Epasto
Vahab Mirrokni? 2 Hoai-An Nguyen Huy L. Nguyen' David P. Woodruff 23 Peilin Zhong²
Abstract
1998). However, its polynomial time and space complexity make it impractical for large-scale datasets. Our goal there- fore is to develop more efficient algorithms for maximum coverage.
In the maximum coverage problem we are given d subsets from a universe [n], and the goal is to output & subsets such that their union covers the largest possible number of distinct items. We present the first algorithm for maximum cover- age in the turnstile streaming model, where up- dates which insert or delete an item from subset come one-by-one. Notably our algorithm only uses poly log update time. We also present turn- stile 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 result of independent interest: an algorithm to estimate the complement of the n!h frequency moment of a vector for 2 2. Empiri- cal evaluation confirms the practicality of our fin- gerprinting algorithms demonstrating a speedup of up to 210x over prior work.
To this end, we present the first one-pass turnstile streaming algorithm for maximum coverage. In the turnstile stream- ing model, updates come one-by-one in 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 poly log n update time to output a near-tight (1 1/ee approximation 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.
1. Introduction
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 cach feature. In targeted fingerprinting, the goal to select fea- tures that minimize the number of users who share identical values with a given target user [n] 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.
Maximum coverage is classic NP-hard problem with ap- plications including information retrieval (Anagnostopoulos et al., 2015), influence maximization (Kempe et al., 2015), and sensor placement (Krause& & Guestrin, 2007). Given d subsets of a universe containing n items and a cardinality constraint k 2 0, the goal is to output the k subsets whose union covers the largest possible number of distinct items. A simple greedy algorithm using (knd) time and O(nd) space achieves tight 1/e relative approximation (as- suming P * NP) by iterating for l rounds and selecting the subset that maximizes the marginal gain at each step (Feige,
Our fingerprinting algorithms fit into the broader privacy attack literature (Seonghun et al., 2023; Chia al., 2019; Zhou et al., 2023) and is an extension of Chia et al. (2019) in privacy auditing and risk measurement. Fingerprinting. which identifies users based on unique attribute combina- tions in a dataset, poses a significant privacy risk. Our algorithms mitigate this risk by identifying the features most likely allow adversaries to successfully fingerprint users. Previous work, except for Gulyás et al. (2016) (whose
'Boston University Gooole Research *Carnegie Mellon Uni- versity "Northeastern University. Correspondence to: Hoai- An Nguyen <hwnguyen@@ndeeeeeee wwwpeenennnwdww...du...... David P. Woodruff <dwoodruf@ wwmp.e.dccc....c........
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Maximum Coverage in Turnstile Streams
algorithms we improve), has only measured the risk of en- tire datasets or fixed sets of features. In contrast, our time and space efficient algorithms are suited for real-time moni- toring of the re- re-identification risks even as dataset evolves. Additionally, targeted fingerprinting is a form of frequency estimation with potential applications in discovering heavy hitters (Bhattacharyya et al.. 2016; Zhu et al., 2020).
et al., 2024), and in more general submodular maximization in the insertion-only set-arrival streaming model (Badani- diyuru et al., 2014; Kazemi et al., 2019). In contrast to all of the above, our algorithm allows arbitrary insertions or dele- tions 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.
Our algorithms are all linear sketches, powerful structures that compress the input matrix while time efficiently han- dling 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 in the coordinator model where there are k distributed ma- chines and one coordinator. The input is split into pieces, and each machine gets 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 distributed ma- chines who can communicate to compute a joint solution. The goal is to again minimize the amount of communication.
There has also been work maximum coverage and sub- modular maximization in the dynamic model (Monem- izadeh, 2020; Chen & Peng, 2022; Lattanzi et al., 2020). We note that these dynamic model algorithms do not achieve sublinear space and in some cases require exponential space. Moreover, they either have a worse update time than our algorithm or do not attain the same approximation quality.
1.2. Our Contributions
Maximum Coverage Results. We formalize the input as an n X d matrix A where entry Aij nonzero if item i is in subset and 0 otherwise. An update takes the form (i dt)), modifying Ai by adding subtracting c.
Theorem 1.1. Given n matrix A, integer 2 0, and E (0. 1), there exists a one-pass turnstile streaming algorithm using (ddee²) space and ((1) update time that outputs (1 1/e - E) relative upproximation to maximum coverage with probability at least 1 - 1/d.
1.1. Related Work
There is an extensive body of work on the maximum cover- age problem, and we only attempt to give an overview of the most relevant works. In the following, an z-relative approx- imation means that the number of distinct items covered by the k subsets outputted by the algorithm is at least x OPT, where OPT is the number of distinct items covered by the optimal solution. Ó(-) notation is used to suppress poly- logarithmic factors in its argument.
Note that the only dependence k in our space complexity is a poly log k factor which is suppressed by the Ô. Our space complexity matches that of Bateni et al. (2017) and, for constant e, that of McGregor & Vu (2019). Additionally, several lower bounds exist. Assadi (2017) show that achiev- ing a (1 - re-lllatvve approximation in a constant number of passes requires Mdde²² space. Assadi & Khanna (2018) show that even achieving a 1/3 or vi relative approxima- tion in one pass with sketch requires the sketch to have size (d/kk)) McGreeo & Vu (2019) shows that achieving better than a (1 (1-14 1/e)- approximation in a constant number of passes requires ((d/k32 ( space. Bateni et al. (2017) also show that any (1/2 + e--relative approximation multi-pas. streaming algorithm requires 2(d) space.
McGregor & Vu (2019) provide a one-pass streaming algo- rithm! that outputs a (1 (1-1/e 1/e- - s)- relative approximation fors E (0, 1) in O(d/=²) 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 sup- ported. Bateni et al. (2017) give a one-pass (1-1/e-e) rel- ative approximation algorithm that uses O(d/e²) memory. They consider the insertion-only streaming model where deletions are not supported. They specifically provide algorithm that carefully samples a number of item-subset relationships and then show that any (a)-relative approx- imation on this smaller subsampled universe achieves a (a reelllatvve approximation for the original input. We use their sketch as starting point.
Fingerprinting Results. In fingerprinting, the input is a d matrix A where A, is the value of user at feature j. An update takes the form (i, it), modifying Aij by adding or subtracting c. We first reduce targeted fingerprinting to maximum coverage to improve upon the ((nd) space and O (kmd) time algorithm of Gulyás et al. (2016). We note that Gulyás et al. (2016) achieve a 1/e approximation.
There has also been work that achieves different approx- imation factors (Saha & Getoor, 2009; McGregor et al., 2021), in random-arrival streams (Warneke et al., 2023; Chakrabarti et al.. 2024), with multiple passes (Chakrabarti
Corollary 1.2. Given a x d matrix A, target user u E [n], and & E (0, 1). there exists a one-pass turnstile streaming algorithm using Ō(d/E²) space and Ô(1) update time that
Sec Appendix A.3 about the streaming model.
outputs a (1 1/e - E) relative approximation to targeted
2

---

Maximum Coverage in Turnstile Streams
fingerprinting with probability at least 1/d.
Theorem 1.3 solve general fingerprinting. The proof of the following is deferred to Appendix E.
We also improve upon the ((nd) space and ((kdd) time algorithm of Gulyás et al. (2016) (which achieves 1/e approximation) for general fingerprinting. While general fingerprinting can be easily reduced to maximum coverage, it requires tracking all (2) user pairs to determine whether they differ in value on certain feature. Upon an update, potentially (n²) user pairs could be affected, making it impractical to use a linear sketch under sublinear space constraints. As a result, we instead design our general fingerprinting algorithm by first designing the following framework for submodular maximization under cardinality constraints over certain functions. The proof of the follow- ing is deferred to Appendix C.
Theorem 1.5. Given a a X matrix A and & E (0, 1),
there exists a one-pass turnstile streaming algorithm using O space and O(k* update time that outputs (1-1/e-z) relative approximation to general fingerpring with probability at least 1 - 1/d.
Experimental Results. We illustrate the practicality of our fingerprinting algorithms by running experiments on two different datasets. In a direct comparison with the imple- mentations of Gulyás et al. (2016), our algorithms show significantly improved efficiency while retaining high com- parative accuracy. Specifically we achieve a speedup of up to 49r and 210x while achieving high comparative accuracy for targeted and generalized fingerprinting, respectively.
Theorem 1.3. Take N to be a set of n items. Let f: :2N Rz0 be monotone, non-negative submodular function. Given input subsets 5,,..., Sa. E N, we aim to maximize J by selecting k subsets. Also take f to be linearly sketchable" with a (1 + r--rlativve approximation in O(8) space. For E E (0, 1), if we set = =e/k then there exists a one-pass turnsttle streaming algorithm which outputs a (1 - -1/e-s)- relative approximation using (ss)) space. The algorithm succeeds with probability at least 1 - 1/ poly(d) if querying the linear sketch of I results in error al most (( poly(ayz)) )
We also show that our general fingerprinting algorithm can serve as dimensionality reduction technique and apply it in the context of feature selection for machine learning models. Since the time complexity of many clustering algo- rithms including k- k-means scales with the dimensionality of dataset, we used our algorithm to select x features that best separate the data. Then we ran k-means on these features instead of the full feature space, showing that we increase efficiency while sacrificing little in accuracy. We believe our techniques to be general and extendable to other clustering and machine learning algorithms outside of h-means.
We then instantiate this framework to solve general finger- printing. To do this, we design a novel linear sketch² for estimating nº- - F3 for p 2 2 on a n dimensional vector æ where F, is the nd frequency moment. If we take 2 to be the set of distinct values in and S, to be the frequency of the 7th distinct value in then Fp = ΣiEz J For example, for
2. Preliminaries
Notation. Some preliminaries postponed to Appendix A. We denote Aij as the entry at the 7th row and jhh column of matrix A. Ō(-) notation suppresses logarithmic factors in its argument. In general we boldface vectors and matrices.
x = (1, 5, 3, 22 3, 3, 3) we have Fp = +1++2++4++1 Here, updates are of the form (i, =c) which performs 3; 4 2% e.
Theorem 1.4. Given a n-diiensional vector x. constant p 2 2, and 7, 5 E (0, 1). there exists a linear sketch of size ÖG7-A²) that supports updates in Ö(,- A time and outputs a (1 + T) relative approximation to np Fp with probability at least 1-5. 5.
Linear Sketches. We begin by defining what a linear sketch is and then provide an overview of the specific linear sketches used in this paper. A more thorough overview is deferred Appendix A. Given a n x matrix A, we can compress it while retaining essential information solve the problem by multiplying it with matrix S. Linear sketches support insertions and deletions to the entries of A as update Gj- This allows us to maintain SA throughout the updates without storing A itself. Furthermore, S is typically stored in an implicit, pseudorandom form (e.g., via hash functions) rather than explicitly, enabling efficient sketching of updates Cij. The update time is the time complexity required for the sketch to process an update.
linear sketching
n² - Fp is the complement of the frequency moment of a dataset (with the error dependent on the complement), and we believe it to be of independent interest. Frequency moments have numerous applications. For example, Fp for p 2 can indicate the degree of the skew of data which is used in the selection of algorithms for data partitioning (DeWitt et al., 1992), error estimation (loannidis & Poosala, 1995), and more. See Alon et al. (1999) for a more in- depth discussion. There are also direct applications for the quantity n" - Fp such as our use of the sketch to instantiate
= SA+Scc holds for any
CountSketch. Next we review the Count-Sketch algorithm for frequency estimation (Charikar et al., 2004). Consider an underlying n--dimensional vector x. The algorithm main- tains a q x B matrix C where B the number of buckets
For the definition of linearly sketchable see Appendix A. "eee Section 2 for more about linear sketches.
3

---

Maximum Coverage in Turnstile Streams
or the sketching dimension. It keeps y distinct hash fune- tions h; [n] [B] and q sign functions 9: : [ri] + {-1,1). The algorithm maintains C' such that ClC, b] = Ejmrt)=D (e) z3. The frequency estimation i; of x; is defined to be the median of {ge(i). C(e, (e))) For- mally, when q
rows of A and processing them in the order determined by the permutation. For each row i in A, subset of (dd((ek) nonzero entries is arbitrarily selected and added to A.. This process continues until A. contains O(d/E") nonzero en- tries in total. So, A, is a carefully subsampled version of A, where only O(d/=)) of the nonzero entries are re- tained while the rest are set to O. We restate their algorithm A. (k, 6) (Algorithm 3) in Appendix B. In Bateni et al. (2017) this subsampled matrix is referred to Hgd-
n²), we have with probability at least simultaneously for all é E [n]. Here z- B/4 denotes vector æ with its top B/4 entries (by magnitude) zeroed out. If æ has only B/4 nonzero entries, with Countsketch using space (B) we can recover all B/4 entries/frequencies exactly. The update time is O(log n).
1 1/pyy(((), |4, x, S 0
|
VB
Bateni et al. (2017) proves that solving the maximum cover- age problem on A. with a-relative approximation guaran- tees a (ax - -reelative approximation on the original matrix A with high probability. The final (1 - 11/e E) -erelattvve ap- proximation is achieved using k-cover (Algorithm 4), which sets appropriate parameters and applies the greedy algorithm (or any (1 1/e) approximation algorithm) A...
To Sketch. Consider an underlying vector x (T)))).TT))) where all entries are initially set to O. We receive m updates of the form v) E [m] x {-M, M) in stream where the update performs Ij f- x2 + v. At the end of the stream, the goal is to output a (1 + 5) relative
Theorem 3.1 (Theorem 2.7 and 3.1 of Bateni et al. (2017)).
Running k-cover with A, produces a (1 - 1/ee - E) ap- proximate solution to maximum coverage with probubility 1/d.
approximation of Lo with probability at least 1 5 where Lo {i : I, o O.}. Kane et al. (2010) give Lo sketch with (1) update time that uses O(s-2 log n (log(1/e) + log ()) log(1/)) memory.
We now present MuiliingAA, (Algorithm 1) where we as- sume we are given complete access to A in its final state along with linear space. Afterwards, we will show how to turn this into a linear sketch which will allow us to efficiently handle updates in sublinear space.
Moment Estimation. Consider an underlying vector a = (x1,-.. ). For all i E [n], 22 E [m]. Let f; Iij : Fy = {}| be the number of occurrences of value in æ. We define the ndh frequency moment of as Fp def >m S for
p 1200 O.
We now prove that building- A. correctly builds A, with high probability. Recall that we want ((d/(=k)) nonzero entries per row until we reach O(d/=²) of them. At a high level, our proof goes as follows. In line 3 we subsample down to a smaller universe A' which only causes us to lose an e factor in our approximation. Now in this smaller universe, in line 7 we hash the rows of A' to a bunch of buckets. In lines 8 18-11 11, from each bucket, we keep a capped number of nonzero entries and store them. Then starting at line 13, we use all our stored nonzero entries to create A,. We will show that the rows of A' are sufficiently spread out among the buckets so that for each row in A' which has nonzero entries, we keep Ö(d/ (sk)(s)) of its nonzero entries. We now present our formal proof.
3. Max- Max-Coverage Algorithm
We now present our sketch, Max-Coverage-LS (Algo- rithm 5). to prove Theorem 1.1. The proofs are deferred to Appendix B. Recall that the input is formalized as a d matrix A, where entry Aij is nonzero if is in subset j, and O otherwise. Our approach uses Algorithm from Bateni et al. (2017) as a starting point. Bateni et al. (2017) reduces the original input matrix A to a smaller universe A, by carefully sampling a subset of its nonzero entries. They then show that running the classical greedy algorithm on this smaller universe yields a (1 1/e- - -e-rettie approxima- tion for the maximum coverage problem on A.
Lemma 3.2. Obtaining an (1 1/e) approximate solu- tion to maximum coverage on A' is an (1 1/e - e/44 approximation solution on A with probability at least 1/ poly
The plan for this section is as follows. We will first introduce the smaller universe A., describing its properties and role in the problem. Next we will show how we construct A. under the assumption that the entire input matrix A in its final state is fully accessible. The construction is done in careful way so that it will be easy to turn into a linear sketch. Finally, we will remove the assumption that A is fully accessible giving us our final algorithm which will efficiently handle updates.
We denote rows of A' 'thtt have at least d/k nonzero entries as "large" and the others as "small". We argue that the number of large items and the total number of nonzero entries among small items is bounded appropriately.
Lemma 3.3. There are at most O log d/ large items in A'.
In the following, note that rows of A and items of A refer to the same thing. Constructing A, involves permuting the
Lemma 3.4. There are O( logg total nonzero entries among small items in A'.
4

---

Maximum Coverage in Turnstile Streams
Algorithm building- A. (n
matrix A, E k0,
1: Set (2 + log d) log log1-=
2: Set =- =/8.
3: Subsample rows from A get A' such that OPT in A' O(klogd/E"). For clarity, row in A' and A both
correspond to the vector that corresponds to item
4: Set ( log
5: Set 0 (log d
6: for = ...., do
7: Use hash function to hash each row of A' to b buckets in structure C..
8: for each bucket in C; do
9: If there are r rows hashed to the bucket, denote the rows concatenated into a vector of length rd as
10: Randomly sample O( dloo((/E)) nonzero entries from and store it in A'-
11: end for
12: end for
13: Initialize A. (k, E) as a n x d matrix with all entries initially set to O.
14: Let P be a random permutation of the rows that are in A'.
15: while the number of nonzero entries in A. (k. E) is less than 24d8' log(1/s) logd do (1-E]ed
16: Process the row j that comes next in P.
17:
Determine among all i E [t] which A; has the most nonzero entries from row j. Take this i to be if row j has less than //og(1//) nonzero entries in A' then Add all of the nonzero entries from row j in AC to (k,
18:
ek
20: else
21: Add d'Iog(1/s) of the nonzero entries from row in A'g, chosen arbitrarily, A, (k. E).
22:
end if
23:
end while
We want to show that for each large item, we recover d (log(1/s)/(e)) of their nonzero entries from A'. In ad- dition, we want to show that for each small item, we recover all their nonzero entries from A'. We refer to any item corresponding to row in A' that contains nonzero entries as "nonzero" item.
Again recall that we must build A, while receiving updates to the entries of underlying matrix A. We first describe our algorithm and give a high level proof review. Then we will present our formal proof. We defer the pseudocode due to length to Appendix B.
In line of Max- Maax-Coeerage-l -LS (Algorithm 5), first keep Lo sketch for each column of A. This will be useful for the final answer our overall algorithm will output for maximum coverage. Then line 6, we use a hash function to subsam- ple rows from to form A', for m E [log n.). Recall that we want to subsample down from A A' such that OPT in A' is O log d/e²). However, we do not know what this sampling rate is since depends the contents of A. Therefore, we subsample at log different levels and form log n different A.. We will later show how to pick which A, we will use.
We begin by proving that each nonzero item is hashed to bucket with no other large item and not too many nonzeros from small items with high probability.
Lemma 3.5. Every nonzero item for some i E [t] is hashed bucket containing
smaller universe
1. no other large item
2. at most O( (llog(1/))
nonzero entries from small items
sk
with probability - 1/ pd)y
Now for each subsampling rate m, we consider the subsam- pled matrix A'm Note that we do not store A', explicitly since this would not in our space allotment. Instead, in this parallel run only consider updates that affect A'm-
So by Lemma 3.5, we recover all nonzero entries from small items and d log(L/e))/et) nonzero entries from each large item present in A' with probability 1 1/ poly (d). Therefore by combining this with Lemma 3.2, we conclude the proof of correctness for building-A...
In line 11, we hash the rows of A', to buckets. Note that we are doing this for to iterations to amplify the probability of success. Then for each bucket we consider the rows hashed there as one long vector v. Again we do not explicitly store this vector rather the structures in this bucket only consider
Our final step is to remove the assumption that we have di- rect access to A. We now show how to implement building- A, via linear sketch, Max- Hax-Coverage-LS (Algorritt (Algorithm 5).
5

---

Maximum Coverage in Turnstile Streams
updates relevant this vector.
items are covered by those subsets. This allows to form our final output. Now present our formal proof.
Recall that in each bucket our goal is to recover O(dlog(1/e) (=))( nonzero entries from vector v. So, in each bucket in lines 13 - 19, we subsample the vector v in log(rd) levels. Then in each level g. we keep an Lo sketch and CountSketch structure with z buckets for Vy. As stated in Section 2, when keeping a CountSketch structure with 4r buckets of vector that contains at most z nonzero entries, the CountSketch will recover those entries exactly. So we want to identify the sampling level o' where v, has at most x entries and query the corresponding CountSketch to recover the appropriate number of nonzero entries from u. Upon a query, we are identifying the appropriate of in line 29. Since an Lo sketch returns how many nonzero entries there are in Uy for some q. we are simply using the Lo sketches to find q/ The rest of the algorithm builds Am,, for m [log nl with our recovered nonzero entries.
Lemma 3.6. Max- Mlax-Coverage-Le (Algorithm 5) and max- coverage (Algoritiu 2) correctly implement building-A, (Algorithm 1) and k-cover (Algorithm 4) with probability at least - 1/ poly(d).
Lemma 3.7. Maximum Coverugee-- uses Ō(d/E²) bits of memory.
Lemma 3.8. The update time of Maximum- is ((1).
Note that we incur only a factor loss in total, resulting in a final 1- 1/e approximation. Specifically, we lose e/4 factor going from A to A', another e/4 factor from running the greedy algorithm on A,, and a //4 factor from using the Lo sketches to determine which set of outputs to return. With Lemma 3.6, Lemma 3.7, and Lemma 3.8, we can now conclude the proof of Theorem 1.1.
We note that in line 25 we state that the Lo sketches and CountSketch structures will handle updates. Recall that Lo sketches and CountSketch structures are both linear sketches. So, they are able to handle insertions and deletions to the vector they are considering. So when an update comes, these linear sketches will update thereby updating our entire linear sketch.
3.1. Targeted Fingerprinting
We now present our proof for Corollary 1.2 via a reduction to maximum coverage. Recall that the input to targeted fingerprinting is n x d matrix A and target user u E [n]. The proof details are deferred to Appendix B.I.
Once we have an Lo sketch for each column of A and all the Am,. for m E [log we perform the following process, max-coverage (Algorithm 2) to get the final answer.
Lemma 3.9. Take A' to be A with the updates Aij Aij - Auj applied for all i E [m], E [d]. For any union of subsets Ut the number of items covered on A' is equivalent to the number of users separated from the target on A.
Algorithm 2 max-coverage
Require: k and & E 1].
Al Algorithmically, we simply run Maximum- Coa-amumm---o-----L--S-
Ensure: A 1 - 1/e - e approximate solution to maximum coverage with probability 1--1/ 1/d.
and alongside store the row that corresponds to target user u in (dd space. After the completion of the updates, we can simulate forming A' from A by sending updates to the max- imum coverage sketch for A. Therefore, the approximation factor, space, and update time all follow from Theorem 1.1 giving us Corollary 1.2.
1: Set s' E/48.
2: For m [log n). construct Am,, (k),')) using Max- Coverage-LS (Algorithm 5). Also store the Lo sketches of the columns of A outputted by Algorithm 5.
3: Run the greedy algorithm (or any 1 approxiaatin algorithm) on each Am,+(k:
4. no - Fp for p 2 2
4: Use the Tog sketches to determine for which Am,, the greedy algorithm gave the best answer and output it.
We prove Theorem 1.4 with p-Tuples-Sketch (Algorithm 7). Since we know n and p, our main goal is to estimate Fy. However, existing work which estimates F, has the error guarantee on Fz. In our problem, we want the error guaran- tee on the complement of Fp (which is n² - Fp). We give a high level algorithm and proof overview. The pseudocode and formal proof are deferred to Appendix D.
max-coverage (A (Algorithm 2) is almost the same as k-cover (Algorithm 4). The difference is we run the classical greedy algorithm on each Am,- for m E [log Now we need to figure out which m corresponded the subsampling rate such that OPT in Am,, is O log d/e?). Instead of doing this, we just use the answer from the Am,, that will give us the best answer
The structures we keep are Lo sketches and a number of perfect to samplers. Recall that an Lo sketch of vector returns the number of nonzero entries of x (with relative (1 () error) and an e sampler of æ returns a nonzero entry exactly uniformly at random. Then, upon an update, since Lo sketches and perfect l, samplers are linear sketches, they
Let us say for some m that running the greedy algorithm on Am, x outputs subsets $1,... $k. We use the Lo sketches corresponding to $1,-..; 8% to estimate how many distinct
6

---

Maximum Coverage in Turnstile Streams
can handle arbitrary insertions//dllttinss to the underlying vector
However, our experiments show that our algorithms still retain good comparative accuracy and greatly increase the time efficiency.
Upon a query, the algorithm does the following to output its final approximation to n² - Fp. First it figures out which value has the highest frequency and estimates this frequency using a Lo sketch and the bn samplers. Querying the Lo sketch and subtracting the result from n gives us the number of O's. The frequencies of the rest of the values can be estimated by looking at their relative frequency among the to samplers (which can be viewed as uniform sample of the entries of x) and scaling it.
Targeted Fingerprinting Results. We made standard mod- ifications that are done in the practical implementation of streaming algorithms. In particular, we use a constant sub- sampling rate p E [.61 instead of subsampling at log rates, and we sample nonzero entries once we are in the smaller subsampled universe with fixed probability as this is sufficient for smaller datasets. All presented data are averages over 10 runs.
Let us call the highest frequency value b and its correspond- ing frequency Js. If fa > n/2, then we will estimate the final approximation fo differently than the rest of the values. Specifically, we subtract off value b from a Lo sketch and then query the result. This gives the number of entries in x that were not equal to value b. Then we set J' to be n minus that result. This is important because it gives us an estimate to fa with y (n - fa) error instead of y fo error.
We present our results for "Adult" with the probability of subsampling rows from to create A' to be p E [0.1, 0.6). One run finds the targeted fingerprint of all users in the dataset for some given k. For k = 7, from Figure I can
Subsampling Probability Time seconds)
Now for the rest of the frequencies, we will again use the fo samplers. We simulate updates that subtract off value from the underlying vector that the to samplers consider. This means that the to samplers are taking uniform samples of æ with b subtracted off all the entries. So when estimating the frequencies of the values besides b using the to samplers after these updates, we have their frequencies with error at most Y (n - fo) instead of additive error yn, For values with very small frequency, we ignore them and show that this does not result in too much error.
3000
time (sec)
2000
sigonthm
this paper
5. Experiments
compai ison
0
0.1
0.2
0.3
0.4
0.5
0.6
subsampling probobility
We outline our fingerprinting results and compare the run- time/accuracy to Gulyás et al. (2016)* 4. We then present our results on dimensionality reduction. All experiments were run locally on M2 MacBook Air. The code can be found here. We use two publicly-availabe datasets, the UC Irvine "Adult" and "US Census Data (1990)" (Becker & Kohavi, 1996; Meek et al.). For consistency, we apply the pre-processing from Gulyás et al. (2016) to both datasets. "Adult" has 32, 561 instances (representing users) and 80 features while "US Census Data (1990)" has 2, 458, 285 instances and 195 features. We note that for fingerprinting do not simulate updates since the algorithms of Gulyás et al. (2016) are not streaming algorithms and therefore un- able to accommodate updates. We also note that we expect the baseline to always achieve better error. This is because we theoretically lose a small e factor in our approximation.
Figure 1. "Adult": subsampling probability vs. time
see that our algorithm runs about 25x, 8.4x, 3x, and 2.3x faster than that of Gulyás et al. (2016) with subsampling probabilities 0.1, 0.2, 0.4, and 0.6 respectively. In settings where n is very large the subsampling probability in our algorithm will be much smaller, and only use larger subsampling probabilities for further insight. Note that the implementation of Gulyás et al. (2016) is deterministic. We put their runtime as a line for visualization. Now we look at accuracy. For increasing ks, we compute the average percent of users our algorithm able to separate from a given target user and compare it to (Gulyás et al., 2016). In Figure 2, we show that we retain good accuracy despite subsampling rows and then subsampling nonzero entries. Note that the vertical axis's 's minimum value is 84%. As the subsampling probability increases, the accuracy of our implementation converges to that of Gulyás et al. (2016).
*(Gulyás ct al., 2016) has two implementations, one of which supposed to be optimized for time. However, we found that the non non-optimizee implementation was faster and therefore use it for comparison.
Now, we present our results for "US Census Data (1990)".
7

---

Maximum Coverage in Turnstile Streams
Cardinality Constraint vs. Percent Users Separated
Cardinality Constraint vs. Percent Users Separated
1.00
1.00
0.98
0.99
percent of total users separated
percent of total users separated
0.98
0.98
0.94
0.97
0.92
0.96
0.90
0.95
0.80
#igorttim compartson
0.94
0.86
C.1
Algoiihm comparison
0.4
0.84
0.6
* - 0.1
0.92
cardinality constraint
cardinality constraint
Figure 2. "Adult"; le vs. accuracy
Figure 3. "US Census Data": vs. accuracy
increases as the sketch size increases. Our implementation is about 210, 120, and 45 times faster than that of Gulyás et al. (2016) for 55, 000, 180, 000, and 400, 000 rows respectively. For a fingerprint of size 20 our implementation takes a little over twice the amount of time as for a fingerprint of size 10. We estimate that the runtime of the comparison algorithm also doubles but cannot be sure due to its non-termination. Concerning accuracy, we again see in Figure 5 that as sketch size increases, the accuracy ratio increases. We make note of a steep drop-off for a sketch with 55, 000 rows. However, our accuracy ratio never dips below 70%.
Due to limited compute, we look at one subsampling level of 0.1. Over 10 runs for 1 = 7, the average time of our algorithm to compute a fingerprint for an input user was 1.06 seconds while the comparison average was 52.6 seconds. The subsampling took an extra 46.355 seconds. So, our algorithm was about 49x times faster. For accuracy, Figure 3 shows that we quickly converge to the accuracy of (Gulyás et al., 2016) with growing k. Note that the vertical axis's minimum value is 92%.
General Fingerprinting Results. The main difference be- tween our theoretical and implemented algorithm is that we only create one sketch rather than It sketches. We first present our results for "Adult". The main variable we vary is the size of our Lo sketch, specifically with 300, 600, 900, and 1, 250 rows. We had our algorithm compute a general fingerprint for k- = 1,2, 20. The runtime of our algo- rithm was largely independent of the size of the sketch and ran in about 0.8 seconds which is 44x faster than the 35.30 second runtime of Gulyás et al. (2016). We measure accu- racy by looking the proportion between the number of pairs of users that our algorithm separates to the number of pairs of users that Gulyás et al. (2016) separates. For each sketch size, we never dip below an accuracy ratio of 80%, and as the sketch size increases the accuracy ratio increases to around 99%. We now present our results for "US Cen- sus Data (1990)". We again vary the size of our La sketch, using 55, 000, 180, 000, and 400, 000 rows. We computed general fingerprint for &- = 1, .., 10. We use smaller l for comparison for this dataset since the implementation of Gulyás et al. (2016) was not able to terminate even after several hours for larger k.
Dimensionality Reduction Results. We use the UCI "Wine" dataset which consists of 1 178 instances and 13 fea- tures (Aeberhard & Forina, 1991). Each of the instances is labeled by one of three wine types. We used our general fingerprinting algorithm to select features that best separate the data. Then, we ran k-means with clusters (for the 3 wine types) using just the selected features. Therefore, this is dimensionality reduction technique, since for many clus- tering algorithms (including k-means and k-means++)) the efficiency depends on the feature dimension. We measure accuracy in the following way. After running k-means on the reduced feature space, for each cluster, we calculate the majority wine type. Then, for each instance, if its actual wine type is not the same as the majority wine type of its assigned cluster, we count it towards the error. We used general fingerprinting to reduce the feature dimension to 3, 4, and features. Our accuracy for all was around 68%.
When running k-means using all 12 features, the accuracy was around 71%, which suggests that we do not introduce that much error. In addition, when running k-means instead on just 3, 4, and completely randomly chosen features, the accuracy decreases to around 52%. We also increase
In Figure& we can see that the runtime of our algorithm
8

---

Maximum Coverage in Turnstile Streams
Sketch Size Time (in seconds)
Cardinality Constraint Accuracy Retio
1.00
Sigorthmm this compet
12000
0.95
10000
accuracy ratio
time(s)
0000
6000
0.85
4000
0.50
2000
55,000
180,000 rows
50000 100000 150000 200000 250000 300000 350000 400000 sketch size (number of CountSketch rows)
2
10
cardinality constraint
Figure 4. "US Census Data": sketch size time
Figure 5. USS Census Data": accuracy
the efficiency of running k-means. Running k-means with our reduced 3, 4, and 5 features compared to running it with all 13 features is about 3.2, 2.4, and 2.1 times faster, respectively.
ity Approximating the Frequency Moments. Comput. Syst. Sei., 58(1):337-147, 1999. doi: 19.1 1545. URL https:// org 10000..006///e. 1997.1545.
Anagnostopoulos, A., Becchetti, I.., Bordino, I,, Leonardi, S., Mele, I., and Sankowski, P. Stochastic Query Covering for Fast Approximate Document Retrieval. ACM Trans. Inf. Syst. 33:3):11:1111:355 2015, doi: 10.1 145//66669967
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
URL https: /toi tttp:/t..o..g////////oo/o//o 11111/1..11111/29991919999
Assadi, S. Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem. In Sallinger, E., den Bussche, J. V., and Geerts, F. (eds.), Proceedings of the 36th ACM
Acknowledgments
Symposium on Principles of Database Systems, PODS 2017, Chicago, IL. USA, May 14-19, 2017, pp. 321-335. ACM, 2017. doi: 10. 10.1145/20334788635551111 URI httpt:ttt///o :/doi..
Hoai-An Nguyen was supported in part by an NSF GRFP fellowship grant number DGE2140739 and NSF CAREER Award CCF-2330255. Huy Nguyen was supported part by NSF award number 231 1649, Alina Ene was supported in part by NSF CAREER award CCF-1750333 and Alfred P. Sloan Research Fellowship.
Assadi, S. and Khanna, S. Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Prob- lem. In Czumaj, A. (ed.), Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium Discrete Al- gorithms, SODA 2018, New Orleans, LA, USA, Jan- uary 7-10, 2018, pp. 2412-2431. SIAM, 2018. doi: 10.1 /t11:7771997111111970111111115 URL https: doi. 0tt.:0111....9911111933300..111.
We thank Sepehr Assadi for numerous helpful discussions. We thank William He for giving many useful presentational comments. We also thank Praneeth Kacham, Noah Singer, and Brian Zhang for helping us review the paper and giving useful comments.
References
Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., and Krause, A. Streaming Submodular Maximization: Mas- sive Data Summarization on the Fly. In Macskassy, S. A., Perlich, C., Leskovec, J., Wang, W., and Ghani, R. (eds.), The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New
Aeberhard, S. and Forina, M. Wine.
UCI DOI:
Machine Learning Repository, 1991.
https//dhi.og/10.2443//55111
Alon, N., Matias, Y., and Szegedy, M. The Space Complex-

---

Maximum Coverage in Turnstile Streams
York, NY, USA -ugustt 24- 27, 2014, pp. 671-680. ACM, 2014. doi: 10. 00.1145/2623333.262666677 URL https: //goo.oog/////////////oo//oo 10.11....115 1et.ei115222222 2623637.
San Francisco, CA, USA, May 19-23, 2019, pp. 350- 364. IEEE, 2019. doi: 10.1109/SP2299.00044. URL 1109/1109/PPP 2019. 00046.
https://doi.
Bateni, M., Esfandiari, H., and Mirrokni, V. S. Almost Optimal Streaming Algorithms for Coverage Problems. In Scheideler, C. and Hajiaghayi, M. T. (eds.), Pro- ceedings of the 29th ACM Symposium on Paralletism in Algorithms and Architectures, SPAA 2017, Wash- ington DC, USA, July 24-26, 2017, pp. 13-23. ACM, URL. https: 3087585.
Witt D. J., Naughton. J. F., Schneider, D. A.. and Se- shadri, S. Practical Skew Handling in Parallel Joins. In Yuan, L. (ed.), 18th International Conference Very Large Data Bases, Augusi 23-27, 1992, Vancou- ver, Canada, Proceedings, pp. 27-40. Morgan Kaufmann, 1992. htthttp: /wwww//wwwwwa/////////////w. vldb org/ conf/1992/
2017. doi: 10.1 00.114//3088555630077335 //doi. org/orgg///.oo/.. 10.
PO27.PDE
Feige, U. A Threshold of In for Approximating Set
Becker, B. and Kohavi, R. Adult. chine Learning Repository, 1996. https///bboor///022442////xx
UCI Ma-
Cover. J. ACM, 45(4):634-652, 1998. doi: 10.
DOI:
1145/285055.285059 URL https: /toaps::/doii /wt. /tt..ooo........////// org/10. 1145/285055 2850559
Bhattacharyya, A., Dey, P., and Woodruff, D. P. An Optimal Algorithm for 11-Heavy Hitters in Insertion Streams and Related Problems. In Milo, T. and Tan, W. (eds.), Proceedings of the 35th ACM SIGMOD- SIGACT-SIGAL Symposium Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 July 01, 2016, pp. 385-400, ACM, 2016, doi: 10. 1145/2902251 URL https: : www.dorr....o.......oo...o..o... 10. 1 20.1145/2902220 2902284..
Gulyás, G. G., Ács, G., and Castelluccia, C. Near-Optimal Fingerprinting with Constraints. Proc. Priv. Enhanc-
ing Technol., 2016(4):470-487, 2016. doi: 10.1515/
SPPETS-2016-0511, URL https: //to:///ooi.oe org/10. 1515 ht15/popets-aoo 2016 60511.
Horel, T. and Singer, Y. Maximization of Approximately Submodular Functions. CoRR, 195/2411.109495 2024. URL https:/
doi: 10.4850/ARXX.2411..0000 doi org/10.gg.ooo 2111111..8855011 48550/550/// aat.ss/arxivvv.. wtt.::iiii211....... 10949.
Chakrabarti, A., McGregor, A., and Wirth, A. Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams. In Chan, T. M., Fischer, J., Iacono, J., and Herman, G. (eds.), 32nd Annual Eu- ropean Symposium
loannidis, Y. E. and Poosala, V. Balancing Histogram Optimality and Practicality for Query Result Size Es- timation. In Carey, M. J. and Schneider, D. A. (eds.), Proceedings of the 1995 ACM SIGMOD International Conference Management of Data, San Jose, Califor- nia, USA, May 22-25, 1995, pp. 233-244. ACM Press, 1995. doi: 10. 10.1145/223784.223841 URL https: wtt..oor/....111//2.... 223.1144422378422234..... 223841.
Algorithmss, ESA 2024, Septem- ber 2-4, 2024, Royal Holloway, London, United King- dom, volume 308 of L/Ples, pp. 40:1-40:15 Schloss Dagstuhl - Zentrumm für Informatik, 2024. doi: 10.42330LIPICS.ESAA 20024.40. URL httpp:://// /doi. org/10. 4230 110330/1100 /LIPIIIIICCCC ESA. 2024.40.
Charikar, M., Chen, K. C., and Farach-Colton. M. Find- ing Frequent Items in Data Streams. Theor. Comput.
Jowhari, H., Saglam, M., and Tardos, G. Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems. In Lenzerini, M. and Schwentick, T. (eds.), Proceedings of the 30th ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pp. 49-58. ACM, 2011. doi: 10.1145/ 1989284.1989289. URL https://doi.org// 1145/1989284. 118942999.....
Sci., 312(1):3-15, 2004. doi: 00.10665000043375500)) 00400-6. URL https: //doss org/10. S0304 3975 (03) 00400-6.
Chen, X. and Peng. B. On the Complexity of Dynamic Submodular Maximization. In Leonardi, S. and Gupta, A. (eds.), STOC '22: 54th Annual ACM SIGACT Sym- posium Theory of Computing, Rome, Italy, June 20 24, 2022, pp. 1685-1698. ACM, 2022. doi: 10. 044535519935.551999 URL https://doi.... 0...11453351999 351 19911.
Kane, D. M., Nelson, J., and Woodruff, D. P. An Optimal Al- gorithm for the Distinct Elements Problem. In Paredaens, J. and Gucht, D. V. (eds.), Proceedings of the Twenty- Ninth ACM
Chia, P. H., Desfontaines, D., Perera, I. M., Simmons- Marengo, D., Li, C. Day, W. Wang, Q., and Gue- vara, M. KHyperLogLog: Estimating Reidentifiabil- ity and Joinability of Large Data at Scale. In 2019 IEEE Symposium on Security and Privacy, SP 2019,
Symposium on Principles of Database Systems, PODS 2010, June 6- 11, 2010, Indianapolis, Indiana, USA, pp. 41-52. ACM, URL https:
2010. doi: 10. 10.114551807088.1887700 //doi. 11 11te://....11111111 1807099
10

---

Maximum Coverage in Turnstile Streams
Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., and Karbasi, A. Submodular Streaming in all its Glory: Tight Approximation, Minimum Memory and Low Adap- tive Complexity. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Confer- ence on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 3311-3320. PMLR, 2019. URL http: / http://ooeeeddiige/e ngs mmm... presss/ v97 /t///aazemiil 9a html.
Monemizadeh, M. Dynamic Submodular Maximiza- tion. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neu- ral Information Processing Systems 33: Anmual Conference on Neural Information Processing Sys- tems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https://proceeeeee neurips. 6 /c/ippppccc/apee//000/aaaa html.
Kempe, D.. Kleinberg, J. M., and Tardos, É. Maximizing the Spread of Influence through a Social Network. Theory Comput., 11:105-147, 2015. doi: 10.4086/T0C.2015. V0114004, URL httpp::/ddo..rgg/// toc. Soc.2015.2 v0110000
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An Analysis of Approximations for Maximizing Submodular Set Functions- I. Math. Program., 14(1):265-294, 1978. doi: 10. 10.1007/BF01588977 URL httpp::////oo.ogg/// 10. 1007 0B0///FF1158899
Krause, A. and Guestrin, C. Near-Optimal Observa- tion Selection using Submodular Functions. In Pro- ceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pp. 1650-1654. AAAI Press, 2007. URL http::/wwwe aaai org wor.oorrg//aaaa...e Library// a0000//aaa0000 07-265.-0265..0 200 php.
Saha, B. and Getoor, L. On Maximum Coverage in the Streaming Model & Application to Multi-Topia Blog- Watch. In Proceedings of the SIAM International Con- ference on Data Mining, SDM 2009, April May 2. 2009, Sparks, Nevada, USA. pp. 697-708. SIAM, 2009. doi: 1T1..011117711997111117779999999 / / oro...rrg/...117/1.
URL https:
Lattanzi, S., Mitrovic, S., Norouzi-Fard, A., Tarnawski, J., and Zadimoghaddam, M. Fully Dynamic Algorithm for Constrained Submodular Optimization. Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: http///epoocceeeeee//ee//
Seonghun, S., Dipta, D. R., and Gülmezoglu, B. De- Defending User Privacy against Cache-based Website Fingerprinting Attacks with Intelligent Noise Injection. In Annual Computer Security Applications Conference, ACSAC 2023, Austin. TX, USA, Decem- ber 4-8, 2023, pp. 379-393. ACM, 2023. doi: 10. 1145/3627106.362711 URL https://doi.cr 10. 10.1145/3627106.22 36271911
fWeb:
neurips.com /t/ http://sccc/pppee////////a 97750044152266aaf334444eeeeee8 html.
Warneke, R., Choudhury, F. M., and Wirth, A. Maxi- mum Coverage in Random-Arrival Streams. In Gørtz, I. L.,, Farach-Colton, M., Puglisi, S. J., and Herman, G. (eds.), 31st Annual European Symposium on Algo- rithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPlcs, pp. 102:1-102:15. Schloss Dagstuhl Zentrrm für Informatik, 2023. URL https:
McGregor, A. and Vu, H. T. Better Streaming Algo- rithms for the Maximum Coverage Problem. Theory Comput. Syst., 63(7):1595-1619, 2019. doi: 10.1007/ 000224-118-877--91 URL https: : http://oo..o//////// 1007/s00024-000
98788 8-x.
doi: 10.442301.PPCSSSSSSA.03... //doi 000022230/// ESA. 2023 102.
McGregor, A., Tench, D., and Vu, H. T. Maximum Coverage in the Data Stream Model: Parameterized and General- ized. In Yi, K. and Wei, Z. (eds.), 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, volume 186 of LIPIcs, pp. 12:1-12:20. Schloss Dagstuhl Leibniz-Zentrun für Informatik, 2021. doi: 10.4230/LIPCCS.IID02220.1 42100..2233311100 12. URL https:://// /ooiooiooooooo/ooooood.o wtt.//0010...43/111t...... ICDT. 2021.12.
Zhou, Q. Wang, L., Zhu, H., and Lu, T. Few-Shot Website Fingerprinting Attack with Cluster Adaptation. Comput. Networks, 229:109788 2023. doi: 10.1016/J.COMNFF 2023. 109780. URL https: : /oi. wwwp...oooo..00..... 1 cownet.e....... 2023 109780.
Zhu, W., Kairouz, P., McMahan, B., Sun, H., and Li, W. Federated Heavy Hitters Discovery with Differential Pri- vacy. In Chiappa, S. and Calandra, R. (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of
Meek, C. Thiesson, B., and Heckerman, D. US Census Data (1990). UCI Machine Learning Repository. DOI: https//do..org/0..433////3

---

Maximum Coverage in Turnstile Streams
Machine Learning Research, pp. 3837-3847. PMLR, 2020. URL http: / /ptp//eedoodgess..eeee..e..e...e m.r. r.peess/ v1 1108//zuu00 hhmml.
12

---

Maximum Coverage in Turnstile Streams
A. Extended Preliminaries
A.1. Linear Sketches
Given a n x d matrix A. we can compress it while retaining essential information to solve the problem by multiplying it with r x n linear sketching matrix S. linear sketch a matrix drawn from a certain family of random matrices independent of A. This independence ensures that S can be generated without prior knowledge of the contents of A. Linear sketches support insertions and deletions the entries of A, as S A + cty) = SA + Seyj holds for any update Cij- which adds or subtracts from an entry of A. This allows us to maintain SAA throughout the updates without storing A itself. Furthermore, S is typically stored in an implicit, pseudorandom form (e.g., via hash functions) rather than explicitly, enabling efficient sketching of updates Cij. The primary focus is on minimizing the space requirement of a linear sketch, specifically ensuring that the sketching dimension r is sublinear in n and ideally much smaller. Another important metric is the update time. Update time refers to the time complexity required for the sketch to process an update.
A.2. Perfect lo Sampling.
Consider an underlying vector x = (Z....., Tn). Let Supp(æ) be the set of nonzero elements of æ. A perfect &o sampler, with probability - 6, returns a tuple (.) for x; E Supp(æ) such that Pr(i = j] = शकाा - n for every j such that Iy E Supp(æ) for large constant c. Note that it returns the value of x; exactly with no error. With probability 8, the sampler outputs FAIL.
An by sampler is a linear sketch and accommodates both insertions and deletions to the underlying vector æ. The parameter n-c can be made arbitrarily small by increasing constant c, effectively making the sampling process indistinguishable from perfect uniform random sampling of nonzero entries on polynomial length streams. Importantly, increasing e incurs only constant factors in space usage. Jowhari et al. (2011) give lo sampler that uses Ollog" log(1/5)) bits of space. By inspecting Theorem 2 of Jowhari et al. (2011) and using appropriate sparse recovery schemes we can see that the update time is poly(log n)- 1og(1/8).
A.3. Streaming Model
In this paper, we represent the input as a n x d matrix A. In the streaming model, it is standard to initialize all the entries to zero before the stream of updates. The algorithm then processes a stream of updates which come one-by-one, each of the form (i, j, tc) for some c. This modifies entry Aij by performing Aij- = Ais + cor Aij = Aij - depending on the sign. We make the standard assumption that each c is at most poly(n).
When the updates can only be positive, this is the insertion-only streaming model. When updates can be both positive and negative this is referred to the turnstile streaming model. The updates can appear in any arbitrary order in the stream, and we make the standard assumption that the length of the stream is at most (oly(n). The goal of the streaming algorithm is to process the stream efficiently, using sublinear space in the size of the input matrix A (and therefore it cannot store all the updates) and a small constant number of passes over the stream. In this work, we restrict our focus to one-pass algorithms. At the end of the stream, the algorithm can do some post-processing and then must output the answer. While streaming algorithms are not required to maintain a stored answer at every point during the stream, there is no restriction on when the stream may terminate. Any time or space used before or after processing the stream is attributed to pre-processing or post-processing, respectively. Generally, our primary focus is on optimizing the memory usage and update time during the stream. Here the update time is the time complexity required by the algorithm to process an update.
1. USEFUL DEFINITIONS
Monotone Submodular Maximization. Consider non-negative set function f 2" + R4. If for all S C CV (e).
f satisfies: f(S U (e}) f(S)= 2 f(TU (e}) - fT)), then of is submodular. We assume that f(0) = 0. If f(S) < (())
for all S C T. then f is also monotone.
Linearly Sketchable Functions. All the functions ʃ 24 + R2 that we consider are of the form S(C) = 9( (a, (ec) where ......, as are a set of vectors that are either fixed in advance or are the columns of the n x d matrix A that is being updated in the stream. We say that a function f is "linearly sketchable" if there exists a randomized sketching matrix S and a corresponding function 9s such that, for any vectors ai...... ad, with high probability for all C [d]. f(C) can be approximated by gs (sS a: hec).
13

---

Maximum Coverage in Turnstile Streams
A.3.2. CONCENTRATION INEQUALITIES
Markov's Inequality.
If X is nonnegative random variable and 0, then
E [
Pr(X a)
a
Chebyshev's Inequality.
For any random variable X and >
Var
Pr([X E
X
B. Deferred Parts of Section (Maximum Coverage)
We restate the algorithm of Bateni et al. (2017), A.,k, 8, 5) (Algorithm 3).
Algorithm 3 A. (k, 6,
Require: f, E (0, 1], and 8. Ensure: c,,
1: Let 8' = 6 log log1-s
2: Let à be an arbitrary hash function that uniformly and independently maps each item (or each row of A) to [0, 1].
3: Initialize A. e,,
4: while number of nonzero entries in A- (k, e, 0) is less than 24d8' log( (og(1/s) log
do (1-s]e²
5: Pick item i of minimum 1<2)) that has not been considered yet.
6: if there are less than dlog(1//)) nonzero entries in the 7th row of A then
7: Add all the nonzero entries from the th row of A to A. 5k,,
8: else
9: Add d'log(1/s) of the nonzero entries of A, chosen arbitrarily, to (k,
ck
10: end if
end while
We now restate the final algorithm from Bateni et al. (2017), k-cover (Algorithm 4).
Algorithm 4 c-covvrr
Require: 4: and & E [0.
Ensure: A (1 - 1/ce - E) approximate solution to maximum coverage with probability 1 1/d.
Set + log d and e' E/12.
2: Construct ( 6))).
3: Run the greedy algorithm (or any 1/e approximation algorithm) Ak, 8) and report the output.
Lemma B.1. Obtaining an (1 1/e) approximate solution to maximum coverage on A' in (1 - (1-1/e-e/4) approximation solution on A with probability at least 1/ (dly
Proof. This states that we only lose e/4 factor by reducing smaller universe via subsampling such that OPT O(k log d/=?). This is proven in McGregor & Vu (2019) in Corollary 9. Note that in McGregor & Vu (2019) they prove (1 - 1/e) approximate solution on A' is an (1 1/c 2e)-apprxiomation solution on A but we re-weigh in our algorithm.
Lemma B.2. There are at most O log d/{²) large items A'.
Proof. Suppose that there are large items. Take S to be the set of these large items. Take P to be the set of the d input subsets. Now we will conduct the following process. First, we choose a subset p1 E P. Suppose that P1 covers ej large items from Recall that "covers" means that those items are subset P1- Now remove pı from P and the ei large items
14

---

Maximum Coverage in Turnstile Streams
covered from S. Now let choose another subset P2 P. Suppose that P2 covers C2 of the (remaining) items in S. Again remove P2 from P and the 02 large items it covered from S. Continue this process for total of & times.
Since we know that OPT = C₁ k log d/ for some constant CJ, it must be that + C + ... + cn S S log d/g//e?. Now, suppose for the sake of contradiction that { = C2 k log d/=² for some constant C2. Then,
C2 - k d/g c2 - _... Cs > C2 k log d/e² - -1 loooolgg// > C2 koo (2E²)
for C2 > 2C1.
So, at each step of the above process, there were at least C2 - loo (2=") large items left in S and therefore at least C2d log d/ (2+2) nonzero entries among those large items. So, the end of the process could have covered k C2 log (2=2² large items. But then we would have
OPT 2 C2/2 . log d/gd Ci dog
which is contradiction.
Lemma B.3. There are O O(dlogd) total nonzero entries among small items in A'.
Proof. Take S to be the set of small items. Take P to be the set of the d input subsets. Suppose that there are total nonzero entries among the items in S. Now we will conduct the following process. First we choose a subset P1 E P. Suppose that p1 covers ej small items from S. Recall that "covers" means that those items are in subset PI. Now remove from P and the C1 small items it covered from S. Now let us choose another subset P2 E P. Suppose that pa covers 02 of the (remaining) items S. Again remove p2 from P and the 02 small items it covered from S. Continue this process for a total of times.
We know that OPT Ci k log d/e" for some constant Cj. Therefore, have that in the above process we removed most
dlogg d g2
tc..... + +c)) k
< C1
edges since we have 01 ... c S ОPT.
Now suppose for the sake of contradiction that C2 - doog d/ for some constant C2. But then, in the above process, each step we could have found a subset covering at least (C2 C1) log d/s² new items. This would mean that we have OPT 2 A (C2- Ci) log d/e² which for appropriate C2 is contradiction.
Lemma B.4. Every nonzero item for some i E is hashed to a bucket containing
1. other large item
2. at most ( (dlo((1/s) 1/6)) ek
nonzero entries from small items
with probability 1 - 1/ (oly(d).
Proof. Consider some nonzero item x. Now consider some iteration i [t].
We will first consider the large items. By Lemma 3.3, there are at most C1 - k log d/s² large items for some constant C1. C₁ has C2 log d/c² buckets. For appropriate C2, we can say that C2 > 4C1. In the worst case, every large item hashed to a different bucket. Then, the probability of æ being hashed to bucket with another large item is at most 1/4.
Now 1et us look the small items. By Lemma 3.4, there are at most (d d/e?) total nonzero entries among small items. Since small items have most d/k nonzero entries, in the worst case there are O log d/e?) = C3 k log d/e² small items each with d/k edges. Recall that C; has C2 A: log d/ e² buckets. Therefore, the expected number of nonzero entries from small items in the same bucket as x is at most C3d/ C2k < 1/4 d k. By Markov's 's inequality. the probability that the actual number of nonzero entries from small items in the same bucket as x is more than d/ k is at most 1/4.
So, the probability that x is hashed to a bucket containing another large item or more than d/ k nonzero entries from small entries is at most 1/2.
15

---

Maximum Coverage in Turnstile Streams
We have Old log(1 (og()/))/((k))) C2 d (loo((/))/ 2 d/k for appropriate C₁ and E (0, 1/2). However note that our proof still holds for the full range of since we can always smaller achieve the desired error bound while only incurring extra constant factor in the space/time.
We hash (log(d//=) times (since we do it for i = ...... t). Lemma 3.3 and Lemma 3.4, we have the result by taking a union bound.
Since we have at most Ó((k + d)/=²) nonzero items by
We show how to implement building- A, via a linear sketch, Max-Coverage-La (Algorithm 5). Lemma B.5. Max-Coverage (Algorithm 5) and max-coverage (Algorithm 2) correctly implement building-A. A., (Algo- rithm 1) and k-cover (Algorithm 4) with probability at least 1 - 1/ poly(d).
Proof. The first step in building-A. is subsampling from to get A' such that OPT in A' is O(k log d/e*). Since this sampling rate depends on what OPT is in A, in Max- Max--ooerraee-SS we instead sample in log n different rates. So in one of the log n different parallel runs, we will sample with the correct rate. We will describe how we choose the right run to consider later.
Let us consider the parallel run with the correct sampling rate. In each iteration i [t], for each bucket, we need to show that we recover x = O (0 log(1/e)) nonzero entries from v. The length of v is rd. So, we subsample log(rd) levels. At each level we keep an Lo sketch python and CountSketch structure with buckets. At some level q' we will have that the number of nonzero entries of ugg I xr 4r/4. We use the Lo sketch to find q'- By the correctness of CountSketch (see Section 2) we will exactly recover the entries of vy Note that we set the failure probability appropriately for the CountSketch structures and Lo sketches so we only incur 1/ poly(d) (d) total error.
ek
So Max- Max-Coverage-LSS (Algorithm 5) produces a Lo sketch for each column of A and Am,. for m E [log We must figure out which Am, is the one that corresponds to the desired subsampling rate. We instead find which A,,* gives us the best answer on the original input A using the To sketches in the following way.
Suppose that for some A,,- the greedy algorithm chooses subsets 81,-.., 8k. We take the Lo sketches for these subsets (or columns of A) and reduce the vector case to estimate how many distinct items these subsets cover in their union.
Imagine that we are working with the original input A. Now, take the original columns $1,..., 3g and concatenate them into a n x k matrix L. We now randomly generate a k x 1 vector æ with entries between [-poly(d), poly Now multiply L by x. We can see with probability at least - 1/ poly(d), the 7h entry in x is nonzero if and only if the 7th row of L is nonzero. So, if the 7th entry of L x nonzero, that means the ,th item was covered by the union of the subsets 81,..., 8k.
Note that L x is by definition equivalent to summing L1 -1-11 + L2 . 32 +... La Ty where L, denotes the 2 column of L and z; denotes the Th entry of æ. Since the Lo sketches that the Lo sketch of the sum of two vectors is equivalent to summing the Lo sketches for the two vectors (see Section 2). Therefore, using the Lo sketches for the d columns of A, we can create the La sketch for L a and query it to get a (1 +//4) approximation to the true coverage of the union of subsets 81,..., 8k-
linear sketches, by definition they have the property
Lemma B.6. Maximum-Coverage uses (dd/=²) bits of memory.
Proof. Keeping Lo sketch for each column of A requires Ödde²)) space total.
The other structures we store are the Lo sketches and CountSketch structures in each bucket. We have log n subsampling instances. In each instance store (b (og()))) buckets for b = O log d/e²). In each bucket store (log(rd)) Ln sketches and O(log(rd)) CountSketch structures with sketching dimension (i.e. the number of buckets in the CountSketch structure) O(dlo((1/s)/(ek)) So the total space requirement of the Lo sketches and CountSketch structures is Ödd=²))
Lemma B.7. The update time of Maximum-CCoverage-S5 is Ô(1).
Proof. We have an Lo sketch for each column of A. Each update will only cause one of these to update. So the update time here is O(1).
16

---

Maximum Coverage in Turnstile Streams
Let's look the update time of the Lo sketches in the buckets. Each update will only cause ((1) of them to update. Note that only one bucket gets affected with an update and we only have to additionally consider the multiple subsampling levels and iterating to boost success probability. So the update time here is (1).
We finally consider the update time of the CountSketch structures in each bucket. Again only one bucket gets affected during an update. So the update time here is also Ó11.
B.1. Targeted Fingerprinting
Lemma B.8. Take A' to be A with the updates Auj Aij Auj applied all i E [m],] E [d]. For any union of subsets U, the number of items covered on A' is equivalent to the number of users separated from the target on A.
Proof. For all i E [ni], for any [d] such that Ag = Auj, we have Alj = 0.. Additionally, for all i E [n]], for any j E [d] such that Aij * Auj. we have that Al is nonzero.
In other words, for all users, for any feature where they shared the same value with the target user u, this entry is now 0. In addition, for any feature where they did not share the same value with the target user, this entry is now nonzero. We can see that the maximum coverage problem on A' exactly corresponds to finding k features which separates the most users from target user u on A.
C. Proof of Theorem 1.3 (Submodular Maximization Framework)
Here, we outline a framework to design algorithms to maximize monotone non-negative submodular functions that are linearly sketchable subject to a cardinality constraint. At a high level we will receive a linear sketch of the input matrix A such that querying the sketch will produce the function's 's output value on some union of subsets. We then adapt the classical greedy algorithm for maximizing a monotone submodular function to query the linear sketches instead of accessing the input matrix directly.
We note that setting 7 = e/k for many linear sketches introduces poly(k) factors in the final memory usage. However, setting 7 = e/k is provably necessary when performing submodular maximization over queried function values that are preserved up to a (1 + 7) factor to achieve a 1 - 1/ee - approximation (see Theorem 5 of Horel & Singer (2024)). Note that this applies to all algorithms that perform submodular maximization that have this property.
We now prove Theorem 1.3. Theorem 1.3 allows us to create an algorithm to maximize a specific monotone non-negative submodular function subject to a cardinality constraint by simply sketching the input A via linear sketch that satisfies the properties of the theorem.
Let C be subset of the column vectors of A. In the following, {S a.) Jiec can be thought of as the sketch of A restricted to C. As described in Appendix 1.3.1, we say that our function f has a corresponding sketching matrix S and gs. Recall that Is gives the answer to a query of function ʃ based on S. For any two subsets of columns X and Y, let gs gs((S as a:)xxx))) denote the marginal gain of adding X, or gs((S a.)eexur) - -g((S aeee). Take c E \ C to denote a column c which is not already in subset C.
(Algorithm 6). We first create k independent linear sketches (recall that the process of creating a linear sketch for the input function is given input to the algorithm). Then we run the following classical greedy submodular maximization algorithm with the modification that instead of directly evaluating the input function f it queries the given sketch. Note that in each of the k adaptive rounds, we use different sketch. The classical greedy algorithm in each round simply looks at all subsets that have not been chosen and adds the one with the largest marginal gain to the output set (Nemhauser et al., 1978).
We now present our algorithm,
sasccyssubmoduulr--aaiiii
We first analyze the memory usage. We are given that each sketch takes O(s) space. Since there are k rounds of adaptivity, the total space taken by the sketches is Osk)). The update time will depend on the specific linear sketch.
Now, let us prove correctness. We assume by our theorem statement that our sketch S and corresponding function gs give us a (1 + 7)-approximation to the queried values of our input function f. There are k adaptive rounds. Since we create as many sketches and use a different one in each round, adaptivity between the rounds does not introduce error. In addition, despite getting (1 + approxximatio to all our queried values instead of the true queried values of our input function, we still get our desired approximation ratio by setting 7 = e/k: This is proven and discussed in Theorem of Horel & Singer
17

---

Maximum Coverage in Turnstile Streams
(2024).
We also get the desired output with probability at least 1 1/ poly(d). Since the enror probability for each function evaluation is O( poly(ary) by union bound over all dk function evaluations, we have an error probability of at most 1 1/ poly(d).
D. Proof of Theorem 1.4 (n² - Fp for 2 2)
We first present the algorithm, p- p-Tuples-Skete Skeech..
Lemma D.1. p-Tuples-Skent Skkechh uses O AA) space and has an update time of Ö(y -))
Proof. We keep two Lo sketches and 2t O p-1 perfect to samplers. Recall that p is a constant.
Now prove correctness. We first give the following result which we will use throughout the proof.
Lemma D.2 (Lemma 3 of Bhattacharyya al. (2016)). Let fs and fe be the frequencies of an item in stream S (of length n) and in random sample T of size from S, respectively. Then for 2 2y log(22 with probability 1 5, for every universe item i simultaneously,
f
J 72
7.
We will assume that all Lo sketches and to samplers succeed in the following, which is true with probability 1 - -33/8. By Lemma D.2, we have that using the lo samplers (from S1 and S2) to estimate the frequencies incurs error at most 26/8. /8. So, we show that we incur at most 36 /8 error in the rest of the algorithm.
For the rest of the analysis, let order the frequencies of the distinet values of vector æ in non-increasing order as fi f2 2 ... fz.
In the algorithm we determine the value of highest frequency and estimate its frequency as f/. If f is too small, we simply output n.. We now show that this is good approximation.
Lemma D.3. ft S Zgo- n, then nP is a (1 7 approximation to n Eiez f..
Proof. Since S yp- n, must be that fa S yot n for all In this case, EiEz f maximized when there 1/7a-t values each with true frequency 7p n. So have
F-T
(1) p-1
ΣS' S Σ iEZ
n)p
'p n² = n..
Recall that in the algorithm we have
P- 16.27
Lemma D.4. For all values v simultaneously. P'. = S's. w1/l / = So + 3en. S's.. denotes the frequency of among the uniform samples which make up St.
Proof. By the correctness L. we have that We (1 + relative approximation to the number of nonzero entries in x. By Lemma D.2, we incur most en additive error for estimating each f" simultaneously using S if w2 the exact number of nonzeros in So the combined error is at most (2s + e²) < 35
In addition, we use L to determine the number of 0's see if O is the value of the largest frequency. This incurs at most
8 n erro. Recall that in the algorithm we output n2 if we estimate f to be less than FT
n. Since by Lemma D.4 and
the correctness of I.J we know the error in estimating each frequency is at most 3e n S 2 n, at worst all values had frequency 7 - n., and we output n?. This does incur too much error by Lemma D.3.
18

---

Maximum Coverage in Turnstile Streams
In the rest of the analysis, we can assume that fi 2 y" 2 n. We now claim that incurring additive y fp (n - (f) error still gives us the desired error guarantee.
Lemma D.5. Incurring 7 y SP- (n f1) error gives us your (n² - Fp) total error.
Proof. We have that n² Fp 2 fo (n - fi) for p 2 2. n" F; counts the number of p-tuples (allowing repetitions) in which not all entries of the tuple have the same value. The right hand side counts p-tuples in which all but one entry equal to the value of highest frequency (i.e. fi) and the last has different value. We can see that the right hand side is a subset of the left hand side. Note that we can assume p S 3 since is a constant. Since we said we could assume that
1
n. we have that / 2 p.
Recall that we find our final approximation of S separately if our initial estimate shows that it is greater than n/22. Specifically, we instead subtract off 5' from Lj and query it to get w2. Then we set fg = n W2. We show that this does not incur too much error.
Lemma D.6. Ii 2 2n, the error incurred from our estimate of J1 is at most
1T-1 (n (n-
Proof. Let us denote the distinct value that has frequency fi in x as b. By Lemma D.4, we incur at most 3R n error in estimating the frequency of b using S₁ (or most E n error if b = O). Since fi 2 2n/3, the next largest frequency is at most n/3. Therefore we will not mistake another value for b. In addition we will estimate f' to be at least n/2.
Since we correctly identify b and correctly determine that its frequency is at least n/2, in our algorithm we will subtract off b from L and then query it to get Wg. Then we estimate the frequency as W2.
Since L3 is a linear sketch, "subtracting off b" means that we simulate updating all the entries of underlying vector x by subtracting from them. Then querying Lj will give us the number of entries æ that are not equal to b.
By the properties of Li we incur at most A(f) = (n f.). Therefore, our total error is at most
(f1 1 (())()))- f= Σ (e) A A-AAN -ff)
Σ
(() p
3=1
<A())
Σ
(
f = A(D 2
3=1
giving us the desired error. Note that estimate of fi could have been f1 A(f) but have ((f + A(F)) RI I(1 A()) -fl-
Let us now consider the case where we do not have fi > 2n/3 but in the algorithm we identify value with estimated frequency f. 2 n/2. By Lemma D.4, we incur at most 35 n eπror in estimating frequencies using S₁ (or by L3 for the value 0). So it must be that f. = (m)) and by the same analysis as Lemma D.6 we get that this does not incur too much error.
We now show that estimating the values of frequency at least
70 I
(n (n-f)) f1)
does not incur too much error. We denote a
set JF which contains every value of with frequency at least I 2
(n- 10-18 fi).
Lemma D.7. The error incurred from estimating ΣiEr f is at most I=th fp-11 (n fi) with probability at least 1-8 8/8.
Proof. We first show how much error we incur by estimating the frequency of one value in F. By Lemma D.2, we incur E(n - fi) error in estimating the frequency if wa had no error in approximating fi. By the correctness of L3 w2 is a (1 + E) multiplicative approximation to f1. Therefore the total error in approximating fr with fsy. w2/t where fs.. is the frequency of i in S2 is at most 3E - (n f1).
By similar reasoning above, even if we choose b incorrectly, we know by Lemma D.4 that fv 2 fo - 66 n. Therefore, subtracting off D' to from S₂ and estimate the frequencies of values in by reweighing e still gets appropriate error. In
19

---

Maximum Coverage in Turnstile Streams
72- (n - f1), we will put addition, note that because in the algorithm we add all values with estimate frequency at least 4 all values that are in in B correctly. We now look at the error incurred estimating all the frequencies values in B.
We denote (fi) = - (n). Let us consider all frequencies except f1. We have that the error is at most
Σ
(UT) - = Σ
[6s + ((A))- Rr
<EB,>>1
Σ
P S (AU)))
Σ
(
E
Σ
(()
iEBi>>1
j=1
iEB,i>1
j=1
<
Σ
A(fi)-2 2
=
RT
Σ
A(Fi).
iEBi>>1
iEB
We will now show that is (Ji) is appropriately bounded. Note that Σie ((f) is the sum of the errors in calculating the frequencies of values in B (except for f1). Following the proof of Lemma D.2, we have E [ r fi and
[ar[f]] & r fi. This gives us E Eipe fi] = r Eif1 Si and VarlE J1 S r Σizı Ia since the covariance of f and f% for j # l is negative. Recall that have Σisz fi Chebyshev's 's (with success amplification) to get that with probability at least 1 - 5/8 we have EieBAsI A(fi) S & (i-fi).
f1 and that set
2) So, can apply
If we had f1 < 2n/3, we get еπrоr (Em) from estimating its frequency from S as proven by Lemma D.4. Since we know that (n - en) & fi I 23/3, by re- re-weighing we get appropriate error.
We now deal with values j such that fj S 1 _ (n - fi). We potentially do not approximate these frequencies. However, their contribution to Σ le is low, and they give us small error as show below.
Lemma D.8. The error incurred by not estimating values with frequency less than
2 (nn is at most 3
Proof. We first observe that we have Eijr fi = fi- So. Σigr Sf is greatest when there are 2 values each with
frequency 7 नo 2 (n f1). So this sum (and therefore the error we incur) most
2/7
P s 2- (n - Si)
Σ
y
(n (n- (n-11 (n--i)
2
i
We have that (n - (1) S np H so we are getting
- (n² SP) total error.
The quantity that we want to estimate is n² - fp- Eisl S. By Jensen's inequality we can see that
S 122 nd - J f1)
n² f8 - -
1>
for some constant 2 2 since we have E f1 n ʃ1 and our summation is over at most 2/7 frequencies. Furthermore, we have that n² SP 2 (n f. So, achieving zه= (np f gives the desired emror guarantee. m
Therefore, combining all the lemmas above gives the result.
E. Proof of Theorem 1.5 (General Fingerprinting)
We now present our algorithm for general fingerprinting, seneral-iigeepprntingg To utilize our general submodular maximization framework from Theorem 1.3, we need to provide a sketch that preserves queried values of the general fingerprinting function to within (1 + 7) factor. The general fingerprinting function receives as input a subset of the columns of A and outputs how many pairs of users they separate. We can therefore see that
(Algorithm 8) to prove Theorem 1.5.
20

---

Maximum Coverage in Turnstile Streams
maximizing this function gives the desired output. Note that the general fingerprinting function is submodular since when adding a new column to set C of columns, if this separates pair of users that were previously not separated, then this column also separates that pair of users if added to some T S C. It is also monotone since adding another column to C never decreases the function value.
Let us analyze the memory usage. We keep two Lo sketches per column of A. As per Theorem 1.3, we must set y = e/k for our sketch. This makes the space of each Lo sketch O(k*/(())))))) So the total space for all d columns is Ō(dk² /²"). The space for each lo sampler is Olog" n). and we keep O(dk? /E²) of them giving us O(dk2/ Using Theorem 1.3, our total space is therefore Ö(dk /=").
For the update time, each update affects one column of A, and therefore two Lo sketches and 0 to samplers. So, the update time per sketch is 9). As per Theorem 1.3, we will keep k sketches so the total update time is Ō(k/>²)= = /E²*
Now, we prove the correctness. As per our framework in Theorem 1.3, our result follows if we can show that our sketch provides (1 >)-approximation to all queried values to our general fingerprinting function with probability O(L(ppolydd))).
Upon a query to our function subset of columns C, we return gs( a, hEc). To do this, for each type of sketch (both the Lo sketch and the lo-sampling sketch) for the columns of subset C, we concatenate them and reduce them each to one column. Below, (SA)c denotes the sketch of A restricted to the columns in C.
Lemma E.1. With probability 1 - 1/(poly(d))))) (d)k), for any rows and y in (S for sketch S, they are distinct if and only if entry and y of [[ are distinct for random vector v with entries in {- poly(ndk)), (oly(ndk)).
Proof: Let us look at two rows of B = -SSAe that are distinct. We call these rows BN and By. Take w to be the vector that is formed from performing BN - By. We first want to show that T v # O.
We have that w = Wi 11 + W2 U22 +... Wt Va Fixing the values of 0n through va-1, there is only one value for Va such that w TT 0. Therefore, this "bad" event happens with probability at most 1/ poly(ndk)). Union bounding over
all possible rows of B, we have that with probability 1/ poly(dk) if rows and y of B for any v, y distinct then entries and y of Bv are distinct.
To finish up the proof, we want to show that if rows x and of B for any y are identical, then entries x and y of Bv are identical. This is clearly true with probability 1.
Now, we are in the vector case. We claim that the rest of the work is done by passing in S₁. S2, Sg. and S₁ into our sketch from Theorem 1.4 with = 2. For each distinct item in the vector, we denote its frequency as ft. As we can see, (b) F2 is the general fingerprinting function. This is because (2) denotes all pairs of users and by subtracting off >, (5) we are subtracting off pairs of users that share identical values. Note the changes in the parameters of the input between here and in Theorem 1.4.
21

---

Maximum Coverage in Turnstile Streams
Algorithm 5 Max-Coverage-L3S (n x matrix A, (0, (0,1),
1: Set (2 + log d) log log1-- n.
2: Set E/8.
3: Keep Lo sketch for each column of A. Denote these La(=) for z [d].
4: for 1.2....... log do
5: {Run in parallel]
6: Use hash function to subsample each row from A with probability 1/2"h. Call the subsampled matrix we consider
this m run A
7: {We do not store A explicitly, This means that the m parallel run we only consider updates to the subsampled rows that form -
8: Set 6 O log -² 9: Set (log )
for 1,...,,o / do
Use a hash function to hash each row A'n to buckets in structure Cm, (We do not store the rows of A/m. explicitly in structure Cm,,-- Rather, each bucket only considers updates the rows that are hashed there.) for each bucket in C,,, do
12:
13:
14:
If there are r rows hashed to the bucket, denote the rows concatenated into a vector of length rd as v.
15:
for q = 1, 2.... .og((r))) do
[Run in parallel)
Use hash function subsample each entry of v with probability 1/24. Call the subsampled vector we consider in this g run v, {we again do not store v, explicitly).
18:
Keep Lo sketch for Vg. Denote it Lo.g. 19: Keep a CountSketch structure with O d log(1/E))
buckets for vg Denote as CS₁,
ck
end for
end for
22:
end for
23:
end for
24:
Set the error probability for each Lo sketch and CountSketch structure such that the total error across all of them is at
most 1/ (oly
25: Upon an update, the Lo sketches and CountSketch structures will handle it.
Upon a query:
for each m [log n| do
28:
Initialize Am, (k,
29:
For each iteration i [t), for each bucket in Cm,,, take the smallest such that querying Lo.g returns number that is (dooR(//s) to q'-
O
=k Take S to be the set of rows of A that have nonzero entries recovered by C.S.²' for any bucket in C,,, for any
iteration [t]. Take to be the of these recovered nonzero entries.
31: Let h be hash function that maps uniformly between [0. 1] the rows in S.
while the number of nonzero entries in Am, (k, a) is less than 24d6' log(1/e) log do
32:
(1-e)e²
33:
Process the row j that comes next in the ordering as determined by hash function h.
if row has less than log((1/)) nonzero entries in P then sk
34:
35:
Add all of the nonzero entries from row j in P to (k,e).
36: else
Add dlog(1/s) of the nonzero entries from row j in P, chosen arbitrarily, to Am,, (k, E).
37:
ek
38: end if
end while
end for
41:
Output Lo(=) for [d] and Am, (k,,) for E [logn].
22

---

Maximum Coverage in Turnstile Streams
Algorithm 6 subbocly- maximmzztinnniniiii
Initialize C 0.
2: while [C] I k do
3: C C- C U en ees axfeed)).
4: end while
5: Return C.
Algorithm 7 p Tepllesle--ketee Sketch (n vector æ, constant integer 2, 7. (0, 1))
p-
16.2"
2: Keep two independent Lo sketches, L3, Lg of each with 8' 5/8 and E.
3: For t 2: log(2()/8)) keep 2t perfect ln samplers of æ. Denote the first t S and the others as S2.
4: Set 8' for each to sampler s.t. the total probability of failure across them is at most 6/8.
5: Upon an update:
6: The Lo sketches and perfect fn samplers will handle updates.
7: Upon a query:
8: Initialize an empty set B.
9: (Estimating the frequency of the highest frequency value, 6.}
10: Query 1. get u1. Set 0 and fg
W1.
11: Estimate the frequency of value using S by taking its frequency in S and scaling by wi/t.
12: Find the value u with highest frequency f' in S.
13: If ff > f/ then +- v and f/ f.
14: If f < I n then output n..
(If frequency
is large enough, estimate separately for appropriate error.)
16: if f/> 2 then
17: Subtract off value from Lß and query it to get u22
18: Set S n
19: end if
20: Add (b. fb) to B.
21: Simulate update v; < x; b E [n]] (Sq will update).
Use S2 to get all values and their frequencies (take the frequency S2 and scale by w2)
23: for all values with frequency f. 4 (n fb) do
24: Add (u, f.) to B.
25: end for
26: Using all tuples (v, f() E B, calculate n² -E and output.
23

---

Maximum Coverage in Turnstile Streams
Algorithm 8 seeeera-fi (n d matrix A, (0, (0,1),k>
1: 7 <e/k.
2: for j E [d] do
3:
Maintain two Lo sketches with s' and Ö(7-2) perfect to samplers for the jdh column of A.
4: end for
5: To answer query:
6: The query will ask for the function value on a subset of columns C.
7: For every j E C, take its first Lo sketch and concatenate them into a matrix (each sketch is a column of the matrix).
Denote the matrix as Sj.
8: For every j C, take second Lo sketch and concatenate them into matrix. Denote the matrix as S2.
9: For each [d]. we view the first half of its Eg samplers uniform sampling vector L1. We view the second half as vector L2.
10: For every j C, take its L1 and concatenate them into matrix Sz.
11: For every j C, take its L2 and concatenate them into matrix S4.
12: Reduce the column dimension of S1, S2, Sz, and S₁ by right multiplying by a random vector v from ) CI_
{- poly(ndkk),.... poly(ndk))
13: Run p-Tuples-Skete Sketch (Algorithm 7) with Si, S2, S3, and S4, 1/(poly(d)k). 7 e/k, and p = 2 to estimate
n² FF
24


Reviews:
[{"review_id": "RYz58qGpCf", "reviewer": "Reviewer_ZvF7", "summary": "This paper studies the maximum coverage problem in the data stream model and give the first turnstile algorithm, i.e., allowing both insertion and deletion, for this problem with space complexity almost match previous insertion-only streaming algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and encouraging comments. We will be sure to adjust the writing, in particular the introduction, to make it more machine learning oriented in the next version of the paper. For example, we will expand on the applications to sensor placement, influence maximization, and engagement maximization which are popular problems in machine learning and have been referenced in other machine learning papers [1, 2].\n\n[1] Zhou, H., Huang, L., and Wang, B. “Improved Approximation Algorithms for k-Submodular Maximization via Multilinear Extension.” ICLR 2025. \n\n[2] Tajdini, A., Jain, L., and Jamieson, K. “Nearly Minimax Optimal Submodular Maximization\nwith Bandit Feedback.” NeurIPS 2024.  \n\nPlease let us know if there is anything else that would be helpful to address or clarify.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have checked the correctness of key proofs. The proofs seem correct to me.", "experimental_designs_or_analyses": "The experimental studies are not the strength of this work. But it made a nice complement to the theoretical results.", "relation_to_broader_scientific_literature": "The key contributions of the paper is presenting the first turnstile streaming algorithms for the max coverage problem and some related problem. Linear sketching techniques are well-studied, but their applications to the problems studied in this paper are missing in the literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:\n1. The main theoretical results are interesting to the streaming literature. In addition to minimizing the space complexity, update time is optimized as well.\n2. Similar techniques are also applicable to fingerprinting problem.\n3. Complementary experimental studies show that the proposed algorithms are competitive.\n\nWeakness:\n1. I feel that the techniques used are not too deep.\n2. The problems studied do not have much \"learning flavor\" (although I have seen similar papers published in top machine learning venues). I think the author could adjust the writing to make it more machine learning oriented.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XiXPfcaGub", "reviewer": "Reviewer_TbWm", "summary": "The paper introduces a linear sketch for the maximum coverage problem that supports both insertions and deletions of item-feature pairs under the turnstile streaming model. This sketch improves on previous work that considers insertion-only streams, or which support only the insertion or deletion of entire subsets rather than individual items from subsets. The main application of this sketch considered in the paper is the fingerprinting problem from the privacy literature, where the task is to select a subset of features that best distinguishes either a single user (i.e., the \"targeted\" case), or all pairs of users (the \"general\" case). As part of the machinery to apply the sketch to general fingerprinting, the paper describes an additional sketch for the complements of frequency moments. The empirical evaluation compares the runtime and accuracy of the proposed sketching approach to the fingerprinting method described in Gulyas et al. (2016). Additionally, an application to accelerate k-means via dimensionality reduction is also explored.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough and encouraging review. We address their comments and questions below. \n\nRegarding the experimental evaluation: \nWe chose Gulyas et al. (2016) as the baseline primarily because it represents the standard offline approach for the fingerprinting application, allowing us to demonstrate the speedup achieved by our sketch. We did not include item deletions in our evaluation because the baseline (prior work Gulyas et al. (2016)) is not a streaming algorithm. Therefore, it does not support updates of any kind including deletions and requires direct access to the entire input (which in this case is input $n \\times d$ matrix $A$). Regarding the penalty of adding support for deletions as compared to prior streaming work - our algorithm achieves the same asymptotic space complexity of $\\tilde{O}(d/\\epsilon^3)$ and near-optimal approximation factor $(1-1/e-\\epsilon)$ as the insertion-only algorithm of Bateni et al. (2017). While constants might differ in practice, theoretically we match the bounds while offering broader functionality. \n\nWe will be sure to improve the formatting and legibility of the plots in the next version of the paper. We thank the reviewer for also pointing out some typos - we will be sure to correct them. \n\nRegarding the question on the sketch from Bateni et al. (2017): \nThe sketch from Bateni et al. (2017) fails to accommodate deletions. Up to $\\tilde{d/\\epsilon^3}$ edges, the sketch requires $d/\\epsilon$ nonzero elements per item/row of input matrix $A$. In particular, in their Algorithm 2 where they implement this sketch in the streaming setting, they keep the first $d/\\epsilon$ nonzeros for some row $r$ and discard all the nonzeros for that row $r$ that come in the stream after this. However, in a stream that has deletions, some subset (or all) of these first $d/\\epsilon$ nonzeros could be deleted, leaving the sketch with no nonzeros for this row. It is not clear how to get around this issue with the algorithm given in the paper of Bateni et al. (2017). \n\nRegarding practical recommendations for selecting parameters for CountSketch and L0 sketches: While our theoretical analysis establishes the necessary parameters to achieve the desired accuracy and failure probability, practical implementations often require less space and time to obtain good approximations. Our experiments support this observation. We set the number of buckets and other sketch-related constants in our implementation to fixed values, which we either varied for experimental analysis or fine-tuned. These values were lower than the theoretical requirements.\n\nRegarding the question about how the algorithm scales: \nIn our experiments we focus on small values of $k$ due to compute limitations. We note that theoretically the only algorithm whose space complexity depends linearly on $k$ is the one for general fingerprinting. In particular, the space of the core max coverage sketch is independent of $k$. In addition, our algorithms are designed for big data settings and we expect our algorithms to scale well with huge values of $n$, $d$, and $k$. Furthermore, as $n,d,k$ grow, we expect the accuracy guarantees to hold while the runtime advantage over the $O(knd)$ baseline becomes more pronounced. Evidence of this can be seen in our speed-up for the larger dataset versus the smaller dataset. \n\nPlease let us know if there is anything else that would be helpful to address or clarify.", "claims_and_evidence": "The claimed construction of a maximum coverage sketch supporting insertions and deletions is supported by the theoretical results. The claim that the sketching approach improves on the fingerprinting method from Gulyas et al. (2016) is supported by the run time and accuracy measurements in the evaluation.", "methods_and_evaluation_criteria": "The fingerprinting evaluation compares the proposed sketch against the method from Gulyas et al. (2016) on the UCI Adult and Census datasets. Two limitations of this evaluation are that: (1) it does not compare the proposed sketch against other sublinear space algorithms for maximum coverage like that of Bateni et al. (2017), which should also be applicable to the fingerprinting problem, and that (2) the evaluation does not touch on the proposed sketch's support for item deletions, which is the main differentiator of this approach from previous work. With respect to (1), one question that should ideally be addressed is: what is the penalty that is incurred vs. prior work in terms of the sketch's memory/accuracy tradeoff due to the added support for deletions?", "theoretical_claims": "I checked the proofs of the main theorems at a high level and did not identify any correctness issues. I did not verify the proofs in detail.", "experimental_designs_or_analyses": "-", "relation_to_broader_scientific_literature": "The paper's contributions are related to the literature on sketching algorithms for performing analyses of data streams using sublinear space. For the maximum coverage problem, the proposed sketch improves on the results of Bateni et al. (2017) by supporting both insertions and deletions while maintaining the same memory cost up to polylog factors.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "Strengths:\n- The theoretical contributions of the paper are strong. The sketch constructions presented in the paper and the accompanying proofs of correctness are nontrivial and will be of interest to the broader streaming algorithms community.\n\nWeaknesses:\n- The empirical evaluation of the proposed sketch is limited, as detailed above.\n- The figures in the evaluation section should be made more legible. The font size in the plots is small, and there is plenty of whitespace that can be filled with larger figures.", "other_comments_or_suggestions": "Typos:\n- L213-214 should read \"This process continues until $A_*$ contains ... So, $A_*$ is ...\".\n- Algorithm 1, L2 should read \"$\\varepsilon = \\epsilon / 8$\"", "questions_for_authors": "1. Can you clarify how the sketch from Bateni et al. (2017) fails to support deletions?\n2. The max coverage sketch is constructed using several Count Sketch and L0 sketches. What practical recommendations do you have for selecting the parameters for these component sketches?\n3. The evaluation section of the paper focuses on small values of $k$. Can you comment on how the algorithm scales to larger values of k, e.g. for dimensionality reduction from 1000s to 100s of features?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "32WJnuvtzb", "reviewer": "Reviewer_gY8Y", "summary": "The paper considers the maximum coverage problem in the turnstile model.\nThe offline problem considers $d$ subsets from a universe $[n]$, and the goal is to output $k < d$ subsets such that the union of the sets contains the largest possible number of items from $[n]$.\nThis can also be expressed in matrix notation where $A\\in\\mathbb{R}^{n\\times d}$: each column is a subset, each row is an item from the universe.\n$A_{ij}\\neq 0$ means that item $i$ is present in subset $j$.\nIn the turnstile model, the matrix is gradually constructed by updates of the form $(i, j, \\pm c)$, modifying $A_{ij}$ by adding or subtracting $c$.\nThe challenge is to continuously solve the maximum coverage problem on $A$ as it gets updated, in low space.\nWithout the restriction on space, the problem is simple, as $A$ can be stored uncompressed and running a greedy algorithm achieves a tight $1-1/e$ relative approximation (assuming $P\\neq NP$), and so we could simply run a greedy algorithm at each step.\nWith a restriction on space, the problem is harder.\n\nPrevious work achieved $(1-1/e -\\epsilon)$-relative approximation for only set-arrival in space $\\tilde{O}(d/\\epsilon^2)$ (McGregor & Vu, 2018).\nBateni et al. (2017), achieved the same error guarantee for item-arrival in space $\\tilde{O}(d/\\epsilon^3)$.\nNeither work supported deletions.\nThis paper gives a streaming algorithm that also supports item-deletion, for the same error guarantee, in $\\tilde{O}(d/\\epsilon^3)$, matching the guarantees of Bateni et al. (2017) for this harder setting (Theorem 1.1).\n\nThe algorithm proposed in this paper uses Bateni et al. (2017) as the starting point.\nThere the idea is that a matrix $A_*$ on a smaller universe can be constructed by carefully subsampling $A$, and that greedily running $k$-cover on $A_*$ gives the right error guarantee.\nIn this paper, they give an algorithm (Algorithm 1) for constructing $A_*$ assuming a fixed $A$ is given up front.\nThey proceed to show how (multiple) $A_*$ can be built from $A$ using a linear sketch (Algorithm 5), internally based on CountSketch and a $L_0$ sketch.\nAs CountSketch and the $L_0$ sketch are linear sketches, and linear sketches support both additions and deletions, so does Algorithm 5.\nWhen outputting an answer, they run $k$-cover on each of the $\\log n$ different (corresponding to different subsampling rates of the rows of $A$) $A_*$, and choose the best output based on the $L_0$ sketch.\n\nThe paper also considers additional problems in turnstile streams.\nThe authors reduce targeted fingerprinting to maximum coverage, thereby improving over an existing algorithm in Gulyas et al. (2016) (Corollary 1.2), reducing space (from $O(nd)$ to $\\tilde{O}(d/\\epsilon^3)$) and time (from $O(knd)$ over all updates, to $\\tilde{O}(1)$ per update).\nFor general fingerprinting, the authors design a new linear sketch for computing the complement of the frequency moment of a dataset, $n^p - F_p$ (Theorem 1.4), which they use for achieving a $(1-1/e-\\epsilon)$-relative approximation for general fingerprinting in space $O(dk^3/\\epsilon^2)$ and time.\n\nThe paper includes experiments on the fingerprinting results run on public datasets, comparing against Gulyas et al. (2016).\nIt is demonstrated that the new algorithms are more time and space efficient (Figure 1, 2 and 4), but at a cost in utility (Figure 2,3 and 5).\nThe authors also demonstrate that their general fingerprinting algorithm can be used for dimensionality reduction, with the use case of $k$-means.\n\n## update after rebuttal\n\nThe authors provided good answers to my questions in their rebuttal. I stand by my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review and comments. We address the comments and questions below. \n\nWe will be sure to scale and format the figures more appropriately in the next version of the paper. \n\nConcerning the $O(\\log n)$ factors in Theorem 1.1: Yes both Bateni et al. (2017) and McGregor & Vu (2018) incur $O(poly \\log n)$ factors. \n\nConcerning the questions on prior work (Gulyas et al., 2016): \n(Gulyas et al., 2016) shows that max coverage can be reduced to fingerprinting proving that fingerprinting is NP-hard. In addition, it is known that the best approximation factor for maximum coverage in polynomial time is $1-1/e$. This is the approximation that (Gulyas et al., 2016) achieves, although it is not proven formally. For both targeted and general fingerprinting their algorithm takes O(nd) space and O(knd) time. In our paper we achieve a $1-1/e-\\epsilon$ approximation for input $\\epsilon \\in (0,1)$, making our approximation near-optimal. In our paper we focus on optimizing the space and time bounds for maximum coverage, giving as a corollary a $\\tilde{O}(d/\\epsilon^3)$ space and $\\tilde{O}(1)$ update time algorithm for targeted fingerprinting. This removes the dependence on $n$ and gives a total time nearly linear in the length of the stream. For general fingerprinting, we achieve $\\tilde{O}(dk^3/\\epsilon^2)$ space. We note that in these big data settings we usually assume that $n$ is much larger than $d$ and therefore aim to remove the space dependence on $n$. We will be sure to make this more clear in the next version of the paper. \n\nFor the experiments, the baseline always does achieve a better error. We will make sure this is clearer in the text. We note that it is expected that the baseline achieves better error - the baseline is a slightly optimized version of the classical greedy maximum coverage algorithm which is known to achieve optimal error for algorithms using polynomial time. However, as noted in our experiments our algorithms do not suffer much in accuracy in comparison and greatly increase the time efficiency. \n\nPlease let us know if there is anything else that would be helpful to address or clarify.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I skimmed the appendix, but did not check any proof carefully.", "experimental_designs_or_analyses": "The experiments performed in the paper make sense to me.", "relation_to_broader_scientific_literature": "To the best of my knowledge, the results are properly contextualized.", "essential_references_not_discussed": "I am not familiar with any missing work.", "other_strengths_and_weaknesses": "Strengths:\n1. It is overall a well-written paper.\n2. The contribution of expanding streaming maximum coverage to also work for deletions strikes me as meaningful, and I personally find the techniques interesting.\n3. The empirical results make a good case for the improved time and space complexity (at a cost in utility).\n\nWeaknesses:\n1. It is hard to infer what was known before on fingerprinting from reading the paper. For targeted fingerprinting Corollary 1.2 and its preceding discussion seem to indicate that this paper improves the space and time complexity, but it is not clear to me if it achieved the same error guarantee. For general fingerprinting it also hard to infer how Theorem 1.5 compares to prior work (Gulyas et al., 2016).\n2. Related to the above, it seems that the baseline always achieves better error in the experiments, but that this should be the case is not clear from the text.\n3. Minor quibble: the figures could be better formatted/scaled.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "I ask the following questions to better understand the contributions made in this paper.\nI do not expect to drastically change my score based on these responses in isolation.\n\nQuestions:\n1. You seem to incur a factor of $O(\\log n)$ in the space from storing $O(\\log n)$ different versions of $A_*$ for the result in Theorem 1.1. Do Bateni et al. (2017) and McGregor & Vu (2018) also incur a logarithmic dependence on $n$?\n2. What error guarantee do Gulyas et al. (2016) achieve for targeted and general fingerprinting? Do they get a $(1-1/e)$-approximation for both?\n3. Is the space/time complexity of Gulyas et al. (2016) the same across general and targeted fingerprinting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uli0MEnowX", "reviewer": "Reviewer_h96F", "summary": "This paper considers the maximum coverage problem, where there is a universe of $n$ elements and we are presented with $d$ subsets of these $n$ elements. The goal is to retain and output a set of $k$ subsets (where $k$ is a parameter given in advance) whose union covers as many items as possible. The exact version of this problem is NP hard, but it is known that a greedy algorithm, which runs in polynomial time, provides a $1-1/e$ approximation, and this is known to be tight assuming $P \\neq NP$.\n\nThis paper considers the setting where the subsets are presented in a (single-pass) streaming fashion: each time we see one subset and the objective is to retain a set of $k$ subsets with approximation factor as close as possible to $1-1/e$ with as little space (memory) as possible. The main result is a single pass algorithm, in a turnstile setting where an element can be added or removed to a single subset in each step. The space complexity for $1-1/e-\\epsilon$ approximation is roughly $d / \\epsilon^3$, and the update time is only polylogarithmic in $n$. The authors also provide applications to fingerprinting, where the goal is to find sets of users satisfying certain \"minimally intersecting\" constraints.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and encouraging comments. We address them below. \nHere is a reference showing that a 1-1/e approximation (unless P = NP) in polynomial time is tight [1]. We will be sure to include this citation in the next version of the paper. \nWe will also be sure to include a more detailed subsection on our proof techniques in the introduction. In particular, we will give an algorithm and proof sketch and more details on why we can accommodate deletions. \n\n[1] Uriel Feige. 1998. A threshold of ln n for approximating set cover. J. ACM 45, 4 (July 1998), 634–652. https://doi.org/10.1145/285055.285059\n\nPlease let us know if there is anything else that would be helpful to address or clarify.", "claims_and_evidence": "This is a theoretical paper and the claims are proved.\n\nCan you provide a reference that $1-1/e$ approx factor is tight? (This was mentioned without proof in the introduction)", "methods_and_evaluation_criteria": "Yes - solid experimental benchmarking (see relevant bullet below).", "theoretical_claims": "The theoretical claims are strong and seem reasonable. I did not verify their correctness.", "experimental_designs_or_analyses": "This is a theoretical paper, and the focus is on proving theorems, not on experimentation. That said, the authors do carry out a number of relevant experiments, which I think is more than enough for such a theoretically-oriented paper. I found the soundness of the experiments adequate, especially given the relatively limited baseline for this problem.", "relation_to_broader_scientific_literature": "There is not a lot of research on this problem in the streaming domain, but the authors do identify the most relevant work and benchmark against it.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "This is a solid paper providing strong results for the maximum coverage problem, with interesting applications to fingerprinting. It is probably worthy of acceptance.\n\nThere are no major weaknesses. Perhaps one minor weakness is that this paper is written in a relatively dry manner, and seems mostly intended for experts. A more detailed subsection on proof techniques (as part of the intro) is also missing and should be added.", "other_comments_or_suggestions": "See weaknesses discussion above.", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: This paper studies the maximum coverage problem and presents a streaming algorithm to solve this problem in the turnstile model, where updates to insert or delete an item arrive one by one. The proposed algorithm uses polylog n update time. 

From the initial reviews, all reviewers were in favor of accepting the paper. Several points to improve the clarity were brought up in reviews:
* limitations of the evaluation: comparisons with other sublinear space algorithms for max coverage and evauating the sketch's support for item deletions. In general, the reviewer hoped to see the question "what is the penalty that is incurred vs. prior work in terms of the sketch's memory/accuracy tradeoff due to the added support for deletions?" addressed.

* More discussion of the literature on fingerprinting that appropriately contextualizes where this contribution lies in the literature. One reviewer wrote: "For targeted fingerprinting Corollary 1.2 and its preceding discussion seem to indicate that this paper improves the space and time complexity, but it is not clear to me if it achieved the same error guarantee. For general fingerprinting it also hard to infer how Theorem 1.5 compares to prior work (Gulyas et al., 2016)."

* Several reviewers commented that the formatting and legibility of the figures should be improved for the final camera ready version.

We encourage the reviewers to revise the final version of the manuscript based on the reviewer comments.
Decision: Accept (poster)