1
$\begingroup$

I have N elements and need to find the maximum of these elements. At each time tick, exactly one of the N elements is updated and I need to determine the new max element (more specifically, the index of the max element). How can I do this by accessing as little "state" as possible?

The naive approach is to store all N elements and in each tick read the N elements and determine the max element. Here the amount of "state" accessed corresponds to N elements.

Is it possible to determine the max element by maintaining lesser state -- specifically state that grows sub-linearly as N increases? Essentially I do not want to make a pass on the entire set of N elements. Assume N is a fixed number.

It seems like this problem has the flavor of data streaming algorithms like the count(-min) sketch. We have N buckets -- items being streamed in update the count of one of these N buckets -- and wish to perform some query on these N buckets with sub-linear space usage.

I understand how sketches can be used to query the value of the Nth bucket, but do not understand if it can be extended to obtain an estimate for the max value (and specifically, the index of the max element). The heavy hitters problem outputs items above a certain frequency, but I am interested only in the item with the maximum frequency.

Am I over-thinking this problem? Is there a far simpler solution?

$\endgroup$
  • $\begingroup$ If the goal is to access as little state as possible, this is not a research-level question; it can be solved with standard data structures taught in undergraduate level CS classes. This can be solved using $O(\lg N)$ time per time tick, and accessing only $O(\lg N)$ elements of state per time tick. Of course, you will need to maintain $\Theta(N)$ state in total, but you only access a small fraction of the state on each time tick. (P.S. The question seems ambiguous: in one place you say you want to minimize the amount of state accessed each tick, in another the amount of state kept total.) $\endgroup$ – D.W. May 14 '14 at 4:14
  • 2
    $\begingroup$ Approximating the maximum within a constant requires $\Omega(N)$ bits of space in the streaming model, even for randomized algorithms. This follows from a simple reduction from the randomized communication complexity of set disjointness and was proved in the classical paper of Alon, Matias and Szegedy. $\endgroup$ – Sasho Nikolov May 14 '14 at 4:16
  • $\begingroup$ @SashoNikolov Answer ? $\endgroup$ – Suresh Venkat May 14 '14 at 6:01
  • $\begingroup$ Thank you for the comments. I see how the wording of the question can be confusing. I had considered the heap before, but as you mentioned it requires maintaining O(N) state. To clarify, I wanted to understand if I can do this without maintaining O(N) state. Sasho Nikolov's answer clarifies this. $\endgroup$ – user22858 May 16 '14 at 3:45
2
$\begingroup$

In the streaming model, any constant approximation of the maximum requires $\Omega(N)$ space. Showing this for a small enough constant approximation follows by an easy reduction from the disjointness problem in two-party communication complexity. This is now very standard, but I will describe it below anyways.

Recall that in the disjointness problem Alice is given a binary string $x \in \{0, 1\}^N$, and Bob is given a string $y \in \{0, 1\}^N$, and they want to decide whether $x$ and $y$ have disjoint support. It is a classic result that this task requires that Alice and Bob exchange at least $\Omega(N)$ bits, even if they share random bits and only want to succeed with probability $2/3$ over the choice of randomness.

Assume there is a randomized streaming algorithm $A$ with space complexity $S$, which with probability $2/3$ computes a number $a$ such that $\frac{a}{F_\infty} \in (\frac{2}{3}, \frac{4}{3})$, where $F_\infty$ is the true maximum frequency of the $N$ elements. This gives a protocol for the disjointness problem with $S$ bits of communication, and therefore $S = \Omega(N)$. In the reduction, Alice simulates the algorithm $A$ and feeds it a stream which increases the frequency of element $i$ by $1$ for each $i$ such that $x_i = 1$. Then Alice takes the memory state of $A$ (which has only $S$ bits) and sends it to Bob, who then simulates $A$ starting from the state he received from Alice and feeds it a stream which increases the frequency of $i$ by $1$ for each $i$ s.t. $y_i = 1$. Then Bob decides that $x$ and $y$ have disjoint support if the output $a$ of $A$ is at most $4/3$.

For more information, see Alon, Matias, and Szegedy's beautiful paper, which introduced the streaming model and proved the first lower bounds.

$\endgroup$
  • $\begingroup$ Thank you for pointing me to this paper and for your explanation. $\endgroup$ – user22858 May 16 '14 at 3:50
1
$\begingroup$

Store all of the items in a max-heap. Updating the value of a single element can be done in $O(\lg N)$ time, accessing at most $O(\lg N)$ elements of state, so you access only $O(\lg N)$ items per time tick. Of course, you maintain $\Theta(N)$ state in total, but you access only a small fraction of the state on each time tick.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy