Practice Problem Set 9 Solutions
Suppose that we want to maintain a random sample of a cash-register-model data stream whose size depends on the number of stream elements seen so far: after seeing \(n\) elements, we should have a sample of size \(\lceil\log_2 n\rceil\), chosen uniformly at random among all possible samples of that size. However, we have no advance knowledge of how big \(n\) is going to be. Explain why, in this scenario, it is not possible to maintain a sketch that allows us to generate samples of the desired size (with the exact probability distribution specified above) using a sublinear amount of space.
(Hint: Find a larger \(N\) for which there is a nonzero probability that the values of all \(n\) items in the current stream will need to be remembered later, after \(N\) elements have been seen.)
Solution: Suppose we have already seen \(n\) elements, and consider what the sample should look like after \(N=2^n\) elements. There is a small but nonzero probability that it will consist of exactly the elements we have already seen, which we cannot generate without storing those elements. But this uses \(n\) words of memory, not a sublinear amount.
For the hierarchical deterministic \(\varepsilon\)-approximation method, how many unmerged blocks would exist after exactly 1000 elements have been added? (Hint: use binary. You do not have to calculate the lengths of the approximations stored for the blocks.)
Solution: The blocks correspond to the nonzero digits in the binary representation of 1000, of sizes 512, 256, 128, 64, 32, and 8. So there are six blocks.
Suppose we have two Boyer–Moore majority sketches \((m_A,c_A)\) and \((m_B,c_B)\) for input sequences \(A\) and \(B\). Explain how to use them to compute a single sketch for the concatenation of sequences \(AB\), again consisting of a pair of numbers \((m,c)\). Your combined sketch does not have to be equal to the sketch that the majority algorithm would produce for \(AB\), but it should provide an estimate for the number \(\operatorname{count}(x)\) of occurrences of each element \(x\) that is bounded between \(\operatorname{count}(x)-|AB|/2\) and \(\operatorname{count}(x)\), just like the majority algorithm would. (In particular, this implies that if \(AB\) has a majority element, your combination will choose that element as its value of \(m\)).
Solution: Produce the sketch that would result from appending \(c_B\) copies of \(m_B\) to sequence \(A\). There are three cases:
If \(m_A=m_B\) keep the same majority element with count \(c_A+c_B\).
If \(m_A\ne m_B\) and \(c_A> c_B\) then keep element \(m_A\) with count \(c_A-c_B\).
In the remaining case keep element \(m_B\) with count \(c_B-c_A\).
Explain how to use this as part of a range query data structure for "range majority" queries. The data structure should maintain a collection of (key,vote) pairs, where the keys are real numbers, and answer queries that ask for the majority vote within some interval of keys. As with the Boyer–Moore majority sketch itself, the answer to any query should be a majority vote if there is one, and can be arbitrary otherwise.
Solution: This is not an associative binary operation, but (because it correctly sketches the concatenation of sequences and concatenation is associative) you can still use it as the underlying operation for a decomposable range query data structure. Store a sketch in each node of a binary search tree, of the sequence of elements in the subtree under that node, and when the sketch of a node needs to be recomputed do so by using the operation described above to combine the sketches of its two children.
The lecture notes for Thursday include the invertible Bloom filter, a somewhat complicated data structure that can report up to \(k\) stragglers (elements that were inserted and then never removed) in a turnstile data stream, for a given parameter \(k\). Describe how to solve the special case of this problem for \(k=1\) using one of the streaming data structures from the lecture notes for Tuesday.
Solution: Use the data structure for finding the average. When a turnstile stream has only one element, its average value is the element itself.