TAOCP 6.5 Exercise 15

The original proof fails because it attempts to collapse the search to a single decoded bucket.

taocpmathematicsalgorithmsvolume-3hm-hard

Section 6.5: Retrieval on Secondary Keys

Exercise 15. [HM30] [HM30] (P. Elias.) Given a large collection of m-bit records, suppose we want to find a record closest to a given search argument, in the sense that it agrees in the most bits. Devise an algorithm for solving this problem efficiently, assuming that an m-bit t-error-correcting code of 2” elements is given, and that each record has been hashed onto one of 2” lists corresponding to the nearest codeword.

Verified: no
Solve time: 4m36s

The original proof fails because it attempts to collapse the search to a single decoded bucket. That step is not justified and is false in general. The correct approach is to treat the codeword partition as a tool for lower bounds, not as a guarantee that the optimum lies in one cell.

Correct Solution

1. Model and partition

Let ${0,1}^m$ be equipped with Hamming distance $d(\cdot,\cdot)$. Let $C \subseteq {0,1}^m$ be a $t$-error-correcting code with $|C| = 2^n$, so that the Hamming balls

$$ B(c,t) = {x : d(x,c)\le t}, \quad c\in C $$

are pairwise disjoint.

Each record $r$ is stored in exactly one list $L[c]$, where $c$ is the unique codeword such that $r \in B(c,t)$. Hence

$$ d(r,c) \le t \quad \text{for } r \in L[c]. $$

Given a query $q \in {0,1}^m$, we want to compute

$$ r^\star = \arg\min_r d(q,r). $$

2. What is true and what is false

The flawed solution incorrectly assumed:

The nearest record to $q$ must lie in the bucket of the nearest codeword to $q$.

This is false because the partition depends on proximity of records to codewords, not proximity to the query.

What is true is only a pair of inequalities:

For any record $r \in L[c]$,

$$ d(q,r) \ge d(q,c) - d(r,c) \ge d(q,c) - t. $$

So each bucket gives a lower bound on all records it contains:

$$ \min_{r \in L[c]} d(q,r) ;\ge; d(q,c) - t. $$

This is the key usable structure.

3. Reformulating the problem correctly

Define for each codeword $c$:

$$ \mathrm{LB}(c) = d(q,c) - t, \quad \mathrm{OPT}(c) = \min_{r \in L[c]} d(q,r). $$

Then:

$$ \mathrm{OPT} = \min_{c \in C} \mathrm{OPT}(c), \quad \text{with} \quad \mathrm{OPT}(c) \ge \mathrm{LB}(c). $$

Thus:

  • codewords with large $d(q,c)$ can be ignored once their lower bound exceeds the best solution found so far,
  • but no single codeword suffices in general.

4. Algorithm

We perform a best-first search over codewords ordered by distance to $q$.

Preprocessing: store all lists $L[c]$.

Query algorithm:

  1. Compute $d(q,c)$ for all $c \in C$, or generate them in increasing order using a priority queue.
  2. Maintain a priority queue of codewords keyed by $d(q,c)$.
  3. Maintain current best distance $D$ and best record $r^\star$, initialized to $D = \infty$.
  4. Extract codewords in increasing order of $d(q,c)$. For each extracted $c$:
  • If $d(q,c) - t \ge D$, stop (pruning condition).
  • Scan list $L[c]$. For each $r \in L[c]$, compute $d(q,r)$ and update $D, r^\star$ if improved.
  1. Return $r^\star$.

5. Correctness proof

Lemma 1 (bucket lower bound)

For any $r \in L[c]$,

$$ d(q,r) \ge d(q,c) - t. $$

Proof. By triangle inequality,

$$ d(q,c) \le d(q,r) + d(r,c) \le d(q,r) + t. $$

Rearranging gives the claim. ∎

Lemma 2 (valid pruning condition)

If for a codeword $c$,

$$ d(q,c) - t \ge D, $$

then no record in $L[c]$ can improve the current best solution.

Proof. For all $r \in L[c]$,

$$ d(q,r) \ge d(q,c) - t \ge D. $$

Hence no improvement is possible. ∎

Lemma 3 (correctness of termination)

When the algorithm stops, all remaining codewords $c$ satisfy

$$ d(q,c) - t \ge D. $$

Thus every unseen record $r$ satisfies $d(q,r) \ge D$, so the current best is globally optimal.

Proof. Every remaining record lies in some bucket $L[c]$, and by Lemma 1 its distance is at least $d(q,c)-t \ge D$. Hence no better record exists. ∎

6. Why the original approach failed

  • It incorrectly equated proximity to a codeword with proximity to the query.
  • It attempted to restrict attention to a single bucket $L[c^\ast]$, which is unjustified.
  • It used triangle inequality bounds that compare unrelated quantities without establishing a global minimum argument.
  • It ignored that optimization must range over all buckets, not a single Voronoi cell.

7. Conclusion

The correct structure is not “search one decoded bucket,” but:

Use the code-induced partition only to derive lower bounds, then perform a best-first search over buckets with pruning.

This yields a correct and efficient nearest-record algorithm under the given coding-based hashing scheme. ∎