Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures

Thank you for your review and feedback. We answer your questions below.

1. Question: What is $F_k$ in the abstract?

This is the $k^{th}$ frequency moment. We have clarified this in the abstract and preliminaries. In the revised version of the paper, we use the parameter $p$ instead of $k$ to avoid overlap with the input parameter $k$ for maximum coverage.

2. Question: The introduction assumes the knowledge about the definition of a sketch. Writing 1-2 sentences defining a sketch before using it in the discussion would be good.

Thank you for the suggestion! We have included this in our revised uploaded paper.

3. Question: The abstract states the space usage to be $O(d/\varepsilon^2)$, but the main theorem (Theorem 1) gives the space-bound as $O(d/\varepsilon^3)$.

Thank you for pointing out this typo. We have fixed it. The space bound is $O(d/\varepsilon^3)$.

4. Question: Remark 1 is unclear and confusing. It starts talking about 'sampling rates', l_0-sampler, etc. without discussing any random process or algorithm. I had no option but to move on without understanding Remark 1.

We apologize for the confusing wording. We have removed Remark 1 from the paper.

5. Question: Lines (141-143): It is unclear what the estimation problem is. Are $x_i$ values given in the streaming setting, or is it $(i, \pm 1)$? Unless this is made clear, I am not sure how to interpret Theorem 3.

We apologize for any confusion here and have provided more clarity before the theorem to specify this. We are getting updates of the form $(i, \pm 1)$.

6. Question: Understanding the sketch algorithm (Algorithm 1) is extremely challenging given that the format of the sketch is not defined. Is $H_{\leq d}$ a matrix or a subset of (element, subset) pairs? How is this sketch updated in the stream on an insertion and deletion? This does not come out clearly from the pseudocode. In line 14 of Algorithm 1, it is said that "sketches and samplers handle updates." Which sketches are these?

We apologize for the confusing wording. We have improved the clarity of the algorithm description and pseudocode of Section 3. Specifically, we first describe our algorithm in a non-streaming and non-low space setting, where we assume direct access to the matrix $A$ in its final state (i.e., no further updates). Here, we prove the algorithm's correctness. We then proceed step by step to demonstrate how to implement this algorithm as a linear sketch that accommodates updates while detailing what exactly is stored in memory at each step.

In regards to your specific question, the algorithm proceeds as follows. We first subsample rows of the input matrix $A$ to form a smaller submatrix $A’$. Importantly, we do not explicitly store these subsampled rows that form $A’$. Rather, we use a hash function to keep track of whether a row has been subsampled to form $A’$. This hash function uses only logarithmic bits of space. Then, whenever an update comes, the run that considers submatrix $A’$ only considers updates to $A’$ (rather than all updates).

Now, consider $A’$. Each row of $A’$ is hashed to a bucket. Again, these rows are not stored explicitly as doing so would require too much space. Instead, we keep a hash function to keep track of which bucket a row has been hashed to. Consider an individual bucket. Suppose that the rows hashed here are those corresponding to items 1, 4, and 5. Then, in this bucket, we will only consider updates to entries that are in the 1st, 4th, or 5th rows. Now, we think of vector $v$ in the following way. Concatenate rows 1,4, and 5 such that the first entries of $v$ are those of row $1$, the next entries are of row $4$, and the last entries are of row $5$. We again do not store $v$ explicitly but instead store $L_0$ samplers for $v$. Each $L_0$ sampler uniformly at random holds a nonzero entry of $v$. These samplers dynamically update to ensure uniformity as updates occur. This is what we mean when we say that samplers and sketches handle updates (since all the samplers and sketches we use are linear sketches themselves). The nonzero entries that the $L_0$ samplers hold will form $A_*$ (previously named $H_{\leq d}$). So, $A_*$ is a subset of the nonzero entries of the original input matrix $A$.

Thank you again for your comments and questions, and please let us know if there is anything else we can clarify.

5. Here $k \log d/\varepsilon^2$ is not OPT in the original input matrix $A$. The first step involves subsampling rows from matrix $A$ to form $A’$ such that the correct sampling rate corresponds to the $A’$ that has OPT value of $k \log d / \varepsilon^2$.

6. It is true that the algorithm of McGregor & Vu relies on the set insertion only model. However, the only part of the proof we use from their paper is the result that we can subsample rows from the matrix $A$ to form submatrix $A’$ such that OPT in $A’$ is $k \log d/\varepsilon^2$, and that solving the problem on $A’$ results in at most an $\varepsilon$ factor loss in our approximation. This is a fairly standard proof which shows that when OPT is at this rate, the number of items in the union of any $k$ subsets is preserved appropriately.

7. $c_1, c_2, \ldots$ are defined within the proof. The process we describe can be understood as follows. Start by considering the set of large items we have. Next, select a subset that covers $c_1$ items, then remove those items and the subset itself. After that, pick another subset that covers $c_1$ items, and repeat this process for $k$ iterations. We use this to prove an upper bound on the number of large items. We use a similar proof to prove an upper bound on the number of edges among small items.

8. You are correct that we are implicitly defining a family of matrices. This is because storing the sketching matrix explicitly would require too much space. Recall that the sketching matrix must have $n$ columns. Therefore, we describe the implicit representation and talk about how updates are performed. You are correct that L_0 samplers need to be linear. They are linear sketches themselves, and we have clarified this in the preliminaries in the revised version of the paper.

Thank you again for your thorough comments, and please let us know if there is anything else we can clarify.

Thank you for your review and feedback. We respond to your questions and comments below.

We apologize for any unclear wording or details. Below, we address your questions directly. Additionally, we have revised the pseudocode and expanded the explanation of the algorithm in Section 3 (maximum coverage) in the revised version of the paper to provide greater clarity.

We also thank you for highlighting these works ([1], [2], and [3]). We note that the referenced studies pertain to the dynamic model, which differs from the streaming model. In the dynamic model, the primary focus is on time complexity, whereas in the streaming model, the emphasis is on achieving sublinear space (though our algorithms also attain sublinear update time). In the revised version of the paper, we have added a brief discussion in the introduction to clarify the distinctions between the dynamic and streaming models.

While we do not run our experiments on a turnstile stream, our primary goal for the proposed linear sketch was to show significant runtime improvements with small memory. We therefore demonstrated these improvements in our experiments all while keeping good comparative accuracy to previous work which used linear memory and time. Since our algorithm is a linear sketch, it will work on any ordering of the entries. In addition, it will accommodate any ordering of updates to the matrix it is applied to.

We now respond to your questions.

1. We do not require the model to be strict-turnstile. Updates take the form $(i, j, +1)$ or $(i, j, -1)$, meaning we either add $1$ or subtract $1$ from entry $(i,j)$ of the input matrix $A$. In addition, our algorithm can support entries of $A$ being both negative and positive. In maximum coverage, we take any non-zero value (including a negative value) at entry $(i,j)$ to mean that item $i$ is covered by subset $j$.

2. We apologize for the typo, and you are correct that we use $L_0$ sketches. To improve clarity, we have revised both the pseudocode and the proof in Section 4 in the revised version.

3. We apologize for any unclear wording. In the revised Section 3, we have improved clarity by reorganizing the explanation. We first describe our algorithm in a non-streaming and non-low space setting, where we assume direct access to the matrix $A$ in its final state (i.e., no further updates). Here, we prove the algorithm's correctness. We then proceed step by step to demonstrate how to implement this algorithm as a linear sketch that accommodates updates where we detail what is stored in each step.

In response to your question, for maximum coverage, we interpret the input matrix $A$ as consisting of nonzeros and 0’s. If entry $(i,j)$ is $0$ in $A$, that means that $j$ does not cover item $i$. If entry $(i,j)$ is $1$ in $A$, that means that $j$ does cover $i$. Note that you can indeed think of any nonzero as a 1 for this purpose. We include nonzeros to make our algorithm more general and also because it is useful for our targeted fingerprinting application.

The algorithm proceeds as follows. We first subsample rows of the input matrix $A$ to form a smaller submatrix $A’$. Importantly, we do not explicitly store these subsampled rows that form $A’$. Rather, we use a hash function to keep track of whether a row has been subsampled to form $A’$. This hash function uses only logarithmic bits of space. Then, whenever an update comes, the run that considers submatrix $A’$ only considers updates to $A’$ (rather than all updates).

Now, consider $A’$. Each row of $A’$ is hashed to a bucket. Again, these rows are not stored explicitly as doing so would require too much space. Instead, we keep a hash function to keep track of which bucket a row has been hashed to. Consider an individual bucket. Suppose that the rows hashed here are those corresponding to items 1, 4, and 5. Then, in this bucket, we will only consider updates to entries that are in the 1st, 4th, or 5th rows. Now, we think of vector $v$ in the following way. Concatenate rows 1,4, and 5 such that the first entries of $v$ are those of row $1$, the next entries are of row $4$, and the last entries are of row $5$. We again do not store $v$ explicitly but instead store $L_0$ samplers for $v$. Each $L_0$ sampler uniformly at random holds a nonzero entry of $v$. These samplers dynamically update to ensure uniformity as updates occur.

In Line 23, we examine all the nonzero entries stored in the $L_0$ samplers that we stored. To construct the final sketch, our goal is to retain ~$d/k$ nonzero entries per row within the subsampled universe $A’$. However, some rows may have started off with fewer nonzero entries (or had none at all). This if statement is accounting for this possibility.

4. This was answered in the response to question 3.

We continue our responses in the next official comment.

Thank you for your review and feedback. In our space analysis, the dependence on $k$ is poly$(\log k)$. Additionally, since the space already includes poly$(\log d)$ factors, and we can assume $k \leq d$ (as $k > d$ allows us to directly output all input subsets), any polylogarithmic factors in $k$ factors are absorbed.

Therefore, when suppressing log factors, we achieve a space complexity of O(d/eps^3) space, consistent with prior work but applicable in a more general model. We apologize for any unclear wording, and we have provided additional clarity on this in the revised version of the paper in the "Our Contributions" section.

Thank you again for your comments and questions, and please let us know if there is anything else we can clarify.

Thank you for your review and feedback. We address your questions and comments below.

Comment/Question: “Some explanation is missing for the algorithm. E.g., the paper claims that algorithm 1 construct a linear sketch. Does this imply that the L_0 sampler used in Algorithm 1 is also a linear sketch? The same question applies to the L_0 sketch. It would be helpful to explicitly clarify whether these sketches are linear, and if they are, to provide brief explanations or references that detail how they function as linear sketches. This additional context would aid readers in understanding the overall linearity of Algorithm 1.”

Thank you for pointing this out. Yes, all the samplers and sketches we use in this paper are linear sketches themselves. We have clarified this in the preliminaries in the revised version of the paper. We have also expanded in the preliminary section of the paper the section on linear sketches. In addition, we have added additional description and clarity to Section 3 for our max coverage algorithm. Specifically, we first describe our algorithm in a non-streaming and non-low space setting, where we assume direct access to the matrix $A$ in its final state (i.e., no further updates). Here, we prove the algorithm's correctness. We then proceed step by step to demonstrate how to implement this algorithm as a linear sketch that accommodates updates while detailing what is stored at each step.

We now address your numbered questions.

1. This is the definition of an $\ell_p$ heavy hitter, which is defined for $p \geq 0$.
2. Thank you for pointing this out. We will fix that typo.
3. We have fixed this typo.

Thank you again for your comments and questions, and please let us know if there is anything else we can clarify.