Priority Sampling

Suppose there are a set of $n$ items with nonnegative weights $w_1, w_2, ..., w_n$ . We want to maintain a subset of samples $S \subset [n]$ in order to answer queries like given arbitrary $I \subset [n]$ , what is $\sum_{i \in I} w_i$ ?

A trivial solution is to set $S = [n]$ and we can answer the query exactly. This is an overkill if our goal is to only answer the query approximately.

Alternatively, we can sample each item $i \in [n]$ independently with probability $p_i$ (to be determined), and maintain a random variable

\begin{aligned} X_i = \begin{cases} \frac{w_i}{p_i} & i \text{ is chosen} \\ 0 & \text{ else } \end{cases} \end{aligned}

Note that

\mathbb{E} \left[ X_i \right] = w_i

And therefore,

\mathbb{E} \left[\sum_{i \in I} X_i \right] = \sum_{i \in I} \mathbb{E}[X_i] = \sum_{i \in I} w_i

Threshold Sampling

One possible implementation of this sampling scheme is called threshold sampling.

First, a threshold $T$ is chosen. Then, for each item $i \in [n]$ , if $w_i \ge T$ , then the algorithm record a value $X_i = w_i$ deterministically. Otherwise, the algorithm record a value $X_i = T$ with probability $\frac{w_i}{T}$ . If $X_i$ is not recorded, it has default value $0$ . In both cases, $\mathbb{E} [ X_i ] = w_i$ .

Mathematically, the two cases can be combined into one. Let $u_i$ be a random number generated between $(0, 1)$ . Then

\begin{aligned} X_i = \begin{cases} \max \{ w_i, T \} & u_i < \frac{w_i}{T} \\ 0 & \text{ else } \end{cases} \end{aligned}

Observe that if $w_i \ge T$ , then $w_i / T \ge 1$ and $X_i \equiv \max \{ w_i, T \} = w_i$ . The expectation of $X_i$ is given algebraically by

\begin{aligned} \mathbb{E} [ X_i ] = \max \{ w_i, T \} \cdot \Pr \left[ u_i \le \frac{w_i}{T} \right] = \max \{ w_i, T \} \cdot \min \{ 1, w_i / T \} = w_i. \end{aligned}

It follows by linearity of expectation that

\mathbb{E} \left[ \sum_{i \in I} X_i \right] = \sum_{i \in I} w_i.

Space Usage

Denote $S$ the set of items with $X_i \neq 0$ and let $p_i$ be the probability of $i$ being sampled. Then the expected size of $S$ is given by

\sum_{i = 1}^n p_i = \sum_{i = 1}^n \min \left\{ 1 , \frac{w_i}{T} \right\}

The problem with threshold sampling is that it is hard to control the memory usage of the sample set $S$ . If the $n$ items are known offline, and we would like $|S| \approx k$ for some integer $k \le n$ , then we can search for some $T$ such that

\sum_{i = 1}^n p_i = k

Then $|S| = k$ in expectation.

The question is, is it possible to force $|S|= k$ exactly? Further, what if the items come online (one by one)?

Priority Sampling

Priority sampling achieves this. First recall that in threshold sampling we decide whether to keep $i$ by checking whether a uniform sampled real number $u_i$ is less than $\frac{w_i}{T}$ :

u_i < \frac{w_i}{T}

This is equivalent to

T < \frac{w_i}{u_i}

Define the priority of an item $i \in [n]$ as $q_i = \frac{w_i}{u_i}$ . Note that $q_i$ is a random variable. In threshold sampling, item $i$ is kept with weight $\max \{ w_i, T \}$ if

T < q_i

Now, instead of using a fixed value of $T$ , the Priority sampling sets

T = (k + 1) \text{-th largest } \{ q_i \}

By the definition of $T$ , only the $k$ items with largest priorities $q_i$ 's are kept in the sample set $S$ :

S = \{ k \text{ items with largest } q_i \text{ 's } \}

It can be seen that $S$ and $T$ can be easily maintained by a binary heap when the items come in stream fashion.

The challenge is not to analyze the behaviors of the r.v.'s:

\begin{aligned} X_i = \begin{cases} \max \{ w_i, T \} & T < \frac{w_i}{u_i} \equiv u_i < \frac{w_i}{T} \\ 0 & \text{ else } \end{cases} \end{aligned}

since now $T$ is itself a random variable.

Theorem

\mathbb{E}[X_i] = w_i.

Proof. There is an elegant proof based on conditional expectation. For $i \in [n]$ , define the random variable $T_i$ as the $k$ -th largest priority of elements other than $i$ . If $i$ -th is sampled, then $q_i \ge T_i$ and $T_i$ becomes the $k+1$ -th largest priority. Therefore,

\mathbb{E}_{X_i} [ X_i \mid T_i ] = \max \{ X_i, T_i \} \cdot \min \{1, w_i / T_i \} = w_i.

Finally, $\mathbb{E}_{X_i} [X_i ] = \mathbb{E}_{T_i} [ \mathbb{E}_{X_i} [ X_i \mid T_i] ] = w_i$ .

Theorem

For $I \subset [n]$ ,

\begin{aligned} \mathbb{E}\left[ \prod_{i \in I} X_i \right] = \begin{cases} \prod_{i \in I} w_i & \text{ if } |I| \le k \\ 0 & else \end{cases} \end{aligned}

Proof: Clearly, when $|I| > k$ , then $\exists i \in I$ , such that $q_i$ is not one of the $k$ largest priorities. Hence $\prod_{i \in I} X_i = 0$ for sure.

If $|I| \le k$ , define $T_I$ to be the $k - |I| + 1$ -th largest priority of elements in $[n] \setminus I$ . Observe that $\prod_{i \in I} X_i \neq 0$ , if only the priorities of all $i \in I$ are among the $k$ largest ones. In such case, $T_I$ becomes the $k+1$ -th largest priority. Therefore,

\mathbb{E} \left[ \prod_{i \in I} X_i \mid T_I \right] = \prod_{i \in I} \mathbb{E} [ X_i \mid T_I ] = \prod_{i \in I} w_i,

and $\mathbb{E}[ \prod_{i \in I} X_i ] = \mathbb{E} [ \mathbb{E} \left[ \prod_{i \in I} X_i \mid T_I \right] ] = \prod_{i \in I} w_i$ .

Reference

Nick Duffield, Carsten Lund, and Mikkel Thorup. Priority sampling for estimation fo arbitrary subset sums. Journal of ACM, 2007
Chandra Chekuri, Lecture note, CS 598: Algorithms for Big Data