Problem

A stream of nn elements indexed by [n]≐{1,2,3,...,n}[n] \doteq \{ 1, 2, 3, ..., n \}. Each element ii is associated with a weight wiw_i.

The goal is to maintain a set SS of mm samples, such that

  1. SS is initialized with {1,2,...,m}\{1, 2, ..., m \};
  2. ∀t>m\forall t > m, when element tt arrives, ∀i∈[t]\forall i \in [t], the ii-th element is kept with probabilitypi≐min⁡{1,wizt}, p_i \doteq \min \left\{ 1, \frac{w_i}{ z_t } \right\}, where ztz_t is the unique solution to the equation ∑i∈[t]pi=m\sum_{i \in [t] } p_i = m, i.e.,∣{i∈[t]∧wi≥zt}∣+∑i∈[t]∧wi<ztwizt=m. \left| \{ i \in [t] \wedge w_i \ge z_t \} \right| + \sum_{ i \in [t] \wedge w_i < z_t } \frac{w_i}{ z_t } = m.

Definition. L(t,x)≐{i∈[t]:wi≥x}L(t, x) \doteq \{ i \in [t ] : w_i \ge x \}.
Definition. W(t,x)≐∑i∈[t],wi<xwiW(t, x) \doteq \sum_{ i \in [t] , w_i < x } w_i.
Definition.

f(t,x)≐∣{i∈[t]∧wi≥x}∣+∑i∈[t],wi<xwix=∣L(t,x)∣+1x⋅W(t,x). \begin{aligned} f(t, x) &\doteq \left| \{ i \in [t] \wedge w_i \ge x \} \right| + \sum_{ i \in [t] , w_i < x } \frac{w_i}{ x } \\ &= \left| L(t, x) \right| + \frac{1}{x} \cdot W(t, x). \end{aligned}

For given t∈[n]t \in [n], ztz_t is the solution to f(t,zt)=mf(t, z_t) = m.

Algorithm

Initially, we can set zt=0z_t = 0 for t∈[m]t \in [m], so that pt=1p_t = 1 and element tt is added to SS.

Next, we discuss how to compute zt+1z_{t + 1} based on ztz_t and how to maintain SS when the t+1t + 1-th element arrives.

Computing zt+1z_{t + 1}

We want to find the solution zt+1z_{t + 1} for the equation f(t+1,x)=mf(t + 1, x ) = m (in which t+1t + 1 is fixed and xx is the variable). First, observe

f(t+1,zt)=f(t,zt)+min⁡{wt+1zt,1}>m. f(t + 1, z_t) = f(t, z_t ) + \min \left\{ \frac{w_{t + 1} }{ z_t}, 1 \right\} > m.

Hence, it holds that zt+1>ztz_{t + 1} > z_t.

W.L.O.G, assume that L(t+1,zt)L(t + 1, z_t) contains kk elements whose weights {x1,x2,..,xk}\{ x_1, x_2, .., x_k \} are sorted in non-decreasing order:

zt≐x0≤x1≤x2≤...≤xk<xk+1≐∞. z_t \doteq x_0 \le x_1 \le x_2 \le ... \le x_k < x_{k + 1} \doteq \infty.

If we fix t+1t + 1, then for x>ztx > z_t, f(t+1,x)f(t + 1, x) is a decreasing and piece-wise linear function on intervals

(x0,x1],(x1,x2],...(xk−1,xk],(xk,xk+1). ( x_0 , x_1 ], ( x_1 , x_2 ], ... ( x_{k - 1} , x_k ] ,( x_k , x_{k + 1} ).

Here if xj−1=xjx_{j - 1} = x_j for some j∈[k]j \in [ k ], then we consider the interval (xj−1,xj](x_{j -1}, x_j ] an empty set and ignore it. If zt+1∈(xj−1,xj]z_{t + 1} \in (x_{j -1}, x_j ], it holds that

f(t+1,xj−1)>m⟺∣L(t+1,xj−1)∣+1xj−1⋅W(t+1,xj−1)>m,f(t+1,xj)≤m⟺∣L(t+1,xj)∣+1xj⋅W(t+1,xj)≤m. \begin{aligned} &f(t + 1, x_{ j - 1 } ) > m &\Longleftrightarrow & \quad | L(t + 1, x_{ j - 1 } ) | + \frac{ 1 }{ x_{ j - 1 } } \cdot W (t + 1, x_{ j - 1 } ) > m, \\ &f(t + 1, x_j ) \le m &\Longleftrightarrow & \quad | L(t + 1, x_j ) | + \frac{ 1 }{ x_{ j } } \cdot W (t + 1, x_{ j } ) \le m . \end{aligned}

When x∈(xj−1,xj]x \in(x_{j -1}, x_j ], ∣L(t+1,x)∣| L (t + 1, x) | is a constant that equals to ∣L(t+1,xj)∣|L(t + 1, x_j )|. We have

∣L(t+1,zt+1)∣+1zt+1⋅W(t+1,zt+1)=∣L(t+1,xj)∣+1zt+1⋅W(t+1,xj)=m. | L(t + 1, z_{t + 1} ) | + \frac{ 1 }{ z_{ t + 1 } } \cdot W(t + 1, z_{ t + 1 } )= | L(t + 1, x_j ) | + \frac{ 1 }{ z_{ t + 1 } } \cdot W(t + 1, x_{ j } ) = m.

Therefore,

zt+1=W(t+1,xj)m−∣L(t+1,xj)∣=∑i∈[t+1],wi<xjwim−∣L(t+1,xj)∣. z_{t + 1} = \frac{ W(t + 1, x_{ j } ) }{ m - \left| L(t + 1, x_j ) \right| } = \frac{ \sum_{ i \in [t + 1], w_i < x_j } w_i }{ m - \left| L(t + 1, x_j ) \right| }.

The following code shows the detailed process for the search of zt+1z_{t + 1}. It maintains

  1. A set LL, such that at the beginning of the algorithm, L=L(t,zt)L = L(t, z_t), and when the algorithm stops, L=L(t+1,zt+1)L = L(t + 1, z_{t + 1} );

  2. The sum of weights WW, which equals to W(t,zt)W(t, z_t) at the beginning of the algorithm, and equals to W(t+1,zt+1)W(t + 1, z_{t + 1} ) when the algorithm stops;

  3. A set CC, which contains elements L(t,zt)∪{t+1}∖L(t+1,zt+1)L(t, z_t) \cup \{ t + 1 \} \setminus L(t + 1, z_{t + 1} ).

Input: a) The weight wt+1w_{t + 1}; b) The set L=L(t,zt)L = L(t, z_t).

  1. C←∅C \leftarrow \emptyset;
  2. If wt+1≥zt:w_{t + 1} \ge z_t:
  3. \qquad L←L∪{t+1}L \leftarrow L \cup \{ t + 1 \}.
  4. Else:
  5. \qquad C←C∪{t+1}C \leftarrow C \cup \{ t + 1 \}.
  6. While ∣L∣≠∅|L| \neq \emptyset and W/min⁡i∈Lwi+∣L∣>m:W / \min_{i \in L } w_i + | L | > m:
  7. \qquad W←W+min⁡i∈LwiW \leftarrow W + \min_{i \in L} w_i;
  8. \qquad move the element i∈Li \in L with minimum wiw_i from LL to CC.
  9. zt+1←W/(m−∣L∣)z_{t + 1} \leftarrow W / (m - |L| ).

Maintaining SS

Denote StS_t the sampled set after tt elements are processed. Define

D=[t]∖L(t,zt),E=St∖L(t,zt). D = [t] \setminus L( t, z_t ), \\ E = S_t \setminus L( t, z_t ).

By definition, it holds that ∣E∣=s−∣L(t,zt)∣=W(t,zt)/zt=∑i∈Dwi/zt|E| = s - |L(t, z_t) | = W(t, z_t ) / { z_t } = \sum_{i \in D} w_i / z_t.

When the element t+1t + 1 comes, let S′≐St∪{t+1}S' \doteq S_t \cup \{ t + 1 \} elements. To obtain a set St+1S_{t + 1}, we need to discard one element in S′S'. Suppose that we have computed zt+1z_{t + 1}. The elements ∈[t+1]\in [t + 1] can be partitioned into three sets:

[t+1]=L(t+1,zt+1)∪C∪D. [ t + 1 ] = L(t + 1, z_{t + 1} ) \cup C \cup D.

Similarly, the set S′S' can be decomposed into three parts:

S′=L(t+1,zt+1)∪C∪E. S' = L(t + 1, z_{t + 1} ) \cup C \cup E.

  1. If i∈L(t+1,zt+1)i \in L(t + 1, z_{t + 1} ), it must be kept in St+1S_{t + 1}.

  2. If i∈Ci \in C, it should be removed with probability 1−wi/zt+11 - w_i / z_{t + 1}. Since i∈Ci \in C, either i=t+1i = t + 1 or i∈L(t,zt)i \in L(t , z_t). In both case, ii appears in S′S' with probability 11. On the other hand, we only keep it with probability wi/zt+1<1w_i / z_{ t + 1} < 1. Let pp be the probability of discarding ii. Then

    1⋅(1−p)=wizt+1. 1 \cdot (1 - p) = \frac{w_i}{ z_{t + 1} }.

    It follows that p=1−wi/zt+1p = 1 - w_i / z_{t + 1}.

  3. If if i∈Ei \in E, then it should be removed with probability p=1−zt/zt+1p = 1 - z_t / z_{t + 1}. Since i∈Ei \in E, it comes from DD and appears in S′S' with probability wi/ztw_i / z_t. As the target probability to keep ii should be wi/zt+1w_i / z_{t + 1}, it holds that

    wizt⋅(1−p)=wizt+1. \frac{w_i}{ z_t } \cdot (1 - p) = \frac{ w_i }{ z_{t + 1} }.

    Therefore, it should be discarded with probability p=1−zt/zt+1p = 1 - z_t / z_{t + 1}.

Finally, we claim that the sum of probabilities to discard an element equals to 1:

∑i∈C(1−wizt+1)+∣E∣⋅(1−ztzt+1)=1. \sum_{i \in C} \left( 1 - \frac{w_i}{ z_{ t + 1} } \right) + |E| \cdot \left( 1 - \frac{z_t}{ z_{t + 1} } \right) = 1.

Proof:

∣S′∣−m=f(t,zt)+1−f(t+1,zt+1)=∣L(t,zt)∣+1zt⋅∑i∈[t],wi<ztwi+1−∣L(t+1,zt+1∣−1zt⋅∑i∈[t+1],wi<zt+1wi=∑i∈C(1−wizt+1)+∑i∈Dwizt(1−ztzt+1)=∑i∈C(1−wizt+1)+∣E∣⋅(1−ztzt+1)=1. \begin{aligned} |S'| - m &= f(t, z_t ) + 1 - f(t + 1, z_{ t + 1} ) \\ &= | L (t, z_t ) | + \frac{1}{z_t} \cdot \sum_{i \in [t], w_i < z_t} w_i + 1 - | L (t + 1, z_{t + 1} | - \frac{1}{z_t} \cdot \sum_{i \in [t + 1], w_i < z_{t + 1} } w_i \\ &= \sum_{i \in C} \left( 1 - \frac{w_i}{ z_{ t + 1} } \right) + \sum_{ i \in D} \frac{w_i }{ z_t } \left( 1 - \frac{z_t}{ z_{t + 1} } \right) \\ &= \sum_{i \in C} \left( 1 - \frac{w_i}{ z_{ t + 1} } \right) + |E| \cdot \left( 1 - \frac{z_t}{ z_{t + 1} } \right) \\ &= 1. \end{aligned}

□\square

To decide which element from C∪EC \cup E to discard, we can run the following pseudo-code:

  1. Sample a real number r∈[0,1]r \in [0, 1] uniformly at random.
  2. For i∈Ci \in C do:
  3. \qquad if r<1−wi/zt+1r < 1 - w_i / z_{t + 1}:
  4. \qquad \qquad discard ii and return;
  5. \qquad else:
  6. \qquad \qquad r←1−wi/zt+1r \leftarrow 1 - w_i / z_{t + 1};
  7. Discard one element from EE uniformly at random;

Reference

[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.