Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures

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$.

This 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.

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.

The paper considers the maximum coverage problem in the turnstile model. The 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]$. This 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. $A_{ij}\neq 0$ means that item $i$ is present in subset $j$. In 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$. The challenge is to continuously solve the maximum coverage problem on $A$ as it gets updated, in low space. Without 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. With a restriction on space, the problem is harder.

Previous work achieved $(1-1/e -\epsilon)$-relative approximation for only set-arrival in space $\tilde{O}(d/\epsilon^2)$ (McGregor & Vu, 2018). Bateni et al. (2017), achieved the same error guarantee for item-arrival in space $\tilde{O}(d/\epsilon^3)$. Neither work supported deletions. This 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).

The algorithm proposed in this paper uses Bateni et al. (2017) as the starting point. There 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. In this paper, they give an algorithm (Algorithm 1) for constructing $A_*$ assuming a fixed $A$ is given up front. They 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. As CountSketch and the $L_0$ sketch are linear sketches, and linear sketches support both additions and deletions, so does Algorithm 5. When 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.

The paper also considers additional problems in turnstile streams. The 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). For 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.

The paper includes experiments on the fingerprinting results run on public datasets, comparing against Gulyas et al. (2016). It 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). The authors also demonstrate that their general fingerprinting algorithm can be used for dimensionality reduction, with the use case of $k$-means.

update after rebuttal

The authors provided good answers to my questions in their rebuttal. I stand by my score.

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.

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.