Nonuniform Sampling

Suppose $S = \{ s_1, s_2, ..., s_m\}$ is a set of samples, with weight $W = \{ w_1, w_2, ..., w_m\}$ and probability $P = \{ p_1, p_2, ..., p_m\}$ .

Now we randomly select an element $X$ from $S$ according to probability $P$ . Define $Y$ the index $X$ . For example, if $X = s_i$ , then $Y = i$ . The expected weight of $X$ is given by

E[w_Y] = \sum_{i \in [1,m]} w_i P( Y = i) = \sum_{i \in [1,m]} w_i p_i

If $P$ is a uniform distribution, i.e., $p_i = 1/m, \ \forall i \in [1,m]$ , then

E[w_Y] = 1 / m * \sum_{i \in [1,m]} w_i

Then $m E[w_Y]$ equals just the sum of $W$ . We say that it is an unbiased estimator of the sum of $W$ . But what if $P$ is not uniform, i.e., $\exists i,j \ s.t., p_i \neq p_j$ .

One technique to remedy this is to construct a new variable $Z_Y = w_Y / p_Y$ .

E[Z_Y] = \sum_{i \in [1,m]} w_i / p_i * P(Y = i) = \sum_{i \in [1,m]} w_i

The strange thing is that how we could know $P = \{ p_1, p_2, ..., p_m\}$ . If we know it in advance, we need not to do sampling to estimate $ \sum_{i \in [1,m]} w_i$.

But in some circumstance, it is possible. To get a random sample $X$ from $S$ , we need to go through some sampling process. Once $X$ is returned, we can calculate the probability of $X$ by examining the sampling process.

[FBKZ16] gives such an example. Consider two relations $R_1 = (A_1, F)$ and $R_2 = (F, A_2)$ , where $R_1.F$ and $R_2.F$ shares the same domain. Let $R = R_1 \bowtie_{R_1.F = R_2.F} R_2$ be the natural join result based on $R_1.F$ and $R_2.F$ . The object is to calculate the sum of attribute $A_2$ on $R = (A_1, F, A_2)$ .

The natural join can be expensive. Is there any way to estimate the join result? Indeed we have.

First sample uniformly at random a tuple $(a_1, f)$ from $R_1$ . The probability of a particular tuple chosen is $1/|R_1|$ , where $|R_1|$ is the number of tuples in $R_1$ .

We further assume that there is an index on $R_2.F$ . So we immediately know the size of the set $R_2[f] \doteq \{ (f, a_2) | (f, a_2) \in R_2 \}$ . We choose uniformly at random a tuple $(f, a_2)$ from $R_2[f]$ and get the join result $(a_1, f, a_2)$ . The probability corresponding to $(a_1, f, a_2)$ is $1/ |R_1| * 1 / R_2[f]$ . So $\frac{a_2}{|R_1| |R_2[f]|}$ is an unbiased estimator of $sum(R.A2)$

Reference
[FBKZ16] Feifei. Li, Bin. Wu, Ke. Yi, Zhuoyue. Zhao, Wander Join: Online Aggregation via Random Walks. SIGMOD'16