Proofs: Multi-probe LSH

The multi-probe sequence is complete and ordered, and probing never lowers the success probability full

This proof shows: correctness.

We use the names of the pseudocode on the page. Fix a table and the query $q$. The gaps satisfy $x_j(-1) \in [0, w)$ and $x_j(+1) = w - x_j(-1) \in (0, w]$, so all are nonnegative. Line L9 sorts the $2M$ pairs $(j, \delta)$ so that $0 \le z_1 \le \cdots \le z_{2M}$, where $z_i$ is the gap of the $i$-th pair. For a nonempty $A \subseteq [2M] = \{1, \ldots, 2M\}$ let $s(A) = \sum_{i \in A} z_i^2$. The set $A$ is valid if no two of its pairs share the same $j$; a valid $A$ names the vector $\Delta(A)$ with $\Delta_j = \delta$ for each pair $(j, \delta)$ of $A$ and $\Delta_j = 0$ otherwise, and then $\mathrm{score}(\Delta(A)) = s(A)$.

Lemma 1 (vectors and valid sets). $A \mapsto \Delta(A)$ is a bijection from the valid nonempty subsets of $[2M]$ onto the nonzero vectors of $\{-1, 0, 1\}^M$.

Proof. A nonzero $\Delta$ comes from the set of the indices of the pairs $(j, \Delta_j)$ with $\Delta_j \ne 0$; this set is valid and nonempty, and it is the only set mapped to $\Delta$, since a valid set holds at most one pair per $j$ and $\Delta$ fixes which. $\square$

Lemma 2 (the generation tree). For a nonempty $A \subseteq [2M]$ with $A \ne \{1\}$ and $m = \max A$, define $\mathrm{par}(A) = A \setminus \{m\}$ if $m - 1 \in A$, and $\mathrm{par}(A) = (A \setminus \{m\}) \cup \{m - 1\}$ otherwise. Then $\mathrm{par}(A)$ is nonempty, $A$ is $\mathrm{expand}(\mathrm{par}(A))$ in the first case and $\mathrm{shift}(\mathrm{par}(A))$ in the second, and $A$ is generated by line L12 from no other set. Following $\mathrm{par}$ from any $A$ reaches $\{1\}$.

Proof. In the first case $\mathrm{par}(A)$ contains $m - 1$, so it is nonempty with maximum $m - 1$, and expanding it adds $m$. In the second case $m \ge 2$, since $A \ne \{1\}$ and $m = 1$ would force $A = \{1\}$; $\mathrm{par}(A)$ contains $m - 1$ and its maximum is $m - 1$, since all other elements of $A$ are below $m - 1$; shifting replaces $m - 1$ by $m$ and gives $A$. Conversely, if $A = \mathrm{expand}(B)$ then $B = A \setminus \{m\}$ and $m - 1 = \max B \in A$; if $A = \mathrm{shift}(B)$ then $B = (A \setminus \{m\}) \cup \{m - 1\}$ with $m - 1 = \max B \notin A$. So the case of $A$ determines the operation and the operation determines $B$. Finally, the quantity $\sum_{i \in A} i$ strictly decreases under $\mathrm{par}$: by $m$ in the first case and by 1 in the second. It is a positive integer, so the chain ends, and it can end only at $\{1\}$, the only set without a parent. $\square$

Lemma 3 (monotone scores). For every $A \ne \{1\}$, $s(\mathrm{par}(A)) \le s(A)$.

Proof. In the first case $s(A) = s(\mathrm{par}(A)) + z_m^2$. In the second $s(A) = s(\mathrm{par}(A)) - z_{m-1}^2 + z_m^2$, and $z_{m-1} \le z_m$ with both nonnegative. $\square$

Lemma 4 (the heap order). The loop of lines L11 to L13, run to the end, extracts every nonempty subset of $[2M]$ exactly once, in nondecreasing order of $s$.

Proof. By Lemma 2 the sets form a tree with root $\{1\}$, the children of $B$ being $\mathrm{shift}(B)$ and $\mathrm{expand}(B)$ when $\max B < 2M$, and line L12 inserts exactly the children of each extracted set. So each set is inserted once, after its parent is extracted, and extracted once: by induction on the depth, every set is eventually inserted, and the heap empties only after all inserted sets are extracted. For the order, suppose $B$ is extracted before $A$ with $s(B) > s(A)$. At the moment $B$ is extracted, $A$ is not yet extracted, so some ancestor $A'$ of $A$, or $A$ itself, is in the heap: the root was inserted, and the first ancestor on the path from the root that is not yet extracted has an extracted parent and so is in the heap. By Lemma 3, $s(A') \le s(A) < s(B)$, which contradicts the choice of $B$ as the minimum. $\square$

Theorem 1 (the sequence). PERTURBATIONS yields every nonzero $\Delta \in \{-1, 0, 1\}^M$ exactly once, in nondecreasing order of score.

Proof. Line L13 yields $\Delta(A)$ for the valid extracted sets. By Lemma 4 each set is extracted once and in nondecreasing order of $s(A) = \mathrm{score}(\Delta(A))$, and by Lemma 1 the valid sets correspond one to one to the nonzero vectors. $\square$

Theorem 2 (the answer). QUERY returns a point of $C$ nearest to $q$, where $C$ is the union, over the $L$ tables, of the home bucket $T_t[g_t(q)]$ and the buckets $T_t[g_t(q) + \Delta]$ for the first $\min(T, 3^M - 1)$ vectors of the sequence; it returns none if $C$ is empty.

Proof. Line L2 stores each point $p$ in $T_t[g_t(p)]$, so $T_t[k]$ is the set of points with key $k$ in table $t$. Lines L6 and L7 add to $C$ exactly the listed buckets, by Theorem 1 for the order. Line L8 takes the minimum. $\square$

Theorem 3 (the success probability). Let $p \in P$ with $\|p - q\| = u$, and let $p(u)$ be the probability that one random function of the family gives $h(p) = h(q)$. For every $T \ge 0$, over the random choice of the functions, $\Pr[p \in C] \ge 1 - (1 - p(u)^M)^L$. If $T \ge 3^M - 1$, then $p \in C$ whenever some table has $|h_{t,j}(p) - h_{t,j}(q)| \le 1$ for all $j$.

Proof. By Theorem 2, $p \in C$ if $g_t(p) = g_t(q)$ for some $t$. The $LM$ functions are independent, so the probability that $g_t(p) = g_t(q)$ is $p(u)^M$ for each $t$, independently over $t$, and the probability that it fails for all $t$ is $(1 - p(u)^M)^L$. For the second statement, with $T \ge 3^M - 1$, Theorem 1 shows that every key $g_t(q) + \Delta$ with $\Delta \in \{-1, 0, 1\}^M$ is probed, and $g_t(p)$ is one of them. $\blacksquare$