Source-linked AI summary
Optimal hash functions for approximate closest pairs on the n-cube
Daniel M. Gordon, Victor Miller, Peter Ostapenko
TL;DR
The paper asks when complete-decoding code hashes can improve on coordinate projection for approximate closest-pair search on the n-cube. It analyzes collision probabilities and error exponents for code-based hashes, including optimal sets, perfect codes, and random codes. It reports that some codes outperform projection, with asymptotically random codes achieving a better error exponent.
Problem
The paper investigates when Golay, Hamming, and other code-based hashes work better than projection for approximate closest-pair search.
Method
The paper compares code-based hashing strategies using complete decoding algorithms, collision probabilities, error exponents, and optimal decoding regions.
Results
For p ∈ (0.2555, 1/2), the Golay code’s error exponent exceeds projection’s, and random codes have higher expected collision probability than projection.
Takeaways & Limitations
Complete-decoding hashes from suitable codes can outperform projection for particular error probabilities, while random codes asymptotically have a better error exponent.
Abstract
from arXiv · showhide
One way to find closest pairs in large datasets is to use hash functions. In recent years locality-sensitive hash functions for various metrics have been given: projecting an n-cube onto k bits is simple hash function that performs well. In this paper we investigate alternatives to projection. For various parameters hash functions given by complete decoding algorithms for codes work better, and asymptotically random codes perform better than projection.
I. INTRODUCTION
The paper studies code-based alternatives to projection for approximate closest-pair search on the n-cube, evaluating collision probabilities through coding-theoretic tools. Its asymptotic conclusion is that random codes can outperform projection.
- Approximate closest-pair search seeks pairs whose Hamming distance is within a factor (1 + ε) of optimal.The problem has applications including information retrieval and DNA sequence comparison.
- Projection onto k coordinates is the standard hash, while complete decoding algorithms for error-correcting codes provide an alternative.A complete decoder maps every n-bit vector to a codeword.
- For a near pair differing by an error vector, the collision probability is PC(p), whereas unrelated pairs collide with probability 2^-k.Hash-table search can repeat with shifted inputs if the desired pair is not found.
- The LSH exponent ρ is optimized by minimizing the near-pair collision probability PC(p).For translation-invariant linear-code decoding, this reduces to studying the set S of vectors decoding to zero.
- ρ = EC(p)/R, and asymptotically random nonlinear codes have a better error exponent than projection.The paper investigates code properties and optimal sets to identify better hashing strategies.
II. HASH FUNCTIONS FROM CODES
The paper evaluates code-based hashes through distance distributions of decoding regions and compares them with coordinate projection. Projection is optimal for sufficiently small error probabilities, despite being a weak error-correcting code.
- Distance distributions count pairs in a decoding region S at each Hamming distance and determine its collision probability under bit errors.For a random x in S, the relevant probability is that x + e remains in S.
- A. Projection: The [n, k] projection hash maps vectors to their selected k coordinates, with S an 2^(n−k)-subcube.Its distance distribution can therefore be analyzed using subcube structure.
- A. Projection: For sufficiently small error probability, projection is an optimal hash even though Pn,k is not a good error-correcting code.Theorem 1 gives the condition p ∈ (0, 2^-2(n−k)).
- A. Projection: The edge isoperimetric inequality shows that among subsets of the same size, subcubes maximize the number of internal edges.Equality holds only for subcubes, supporting projection’s small-error optimality.
B. Concatenated Hashes
Concatenating hashes combines code-based mappings over separate coordinate blocks. The paper establishes that combining good hashes preserves the relevant performance comparison.
- B. Concatenated Hashes: A hash h and a second hash h′ can be concatenated into a hash on n + n′ bits with output dimension k + k′.The construction treats the two code outputs as a joint codeword.
- B. Concatenated Hashes: For fixed p, concatenation preserves the ordering of hashes by error exponent, with strict improvement when the component exponents differ.The comparison assumes Eh ≤ Eh′ in the proof.
C. Perfect Codes
Perfect codes provide uniquely decodable error-correcting regions that can serve as hashing schemes. Golay and Hamming codes perform well, with Golay beating projection over a substantial high-error range.
- C. Perfect Codes: A perfect [n, k, 2e + 1] code has error spheres around codewords that cover the entire cube, making minimum-weight decoding unique.Only trivial repetition, Hamming, and binary Golay codes are perfect over the binary cube.
- C. Perfect Codes: The [23, 12, 7] binary Golay code is a notable perfect code whose 3-spheres cover F2^23.
- 1) Binary Golay Code:: For p ∈ (0.2555, 1/2), the Golay code’s error exponent exceeds that of projection.
2) Hamming Codes:
Hamming codes can outperform projection above a parameter-dependent crossover error probability. The analysis identifies a unique crossover threshold and bounds it for sufficiently large code dimensions.
- Table I reports crossover error probabilities where the first Hamming codes become better than projection.
- For m > 4 and p > m/(2^m − m), the Hamming code Hm beats (2^m − m − 1)-projection.
- For m ≥ 4, the comparison polynomial fm(ζ) has exactly one root αm in (0, 1), with αm ∈ ((m − 2)/2^m, m/2^m).
- For p > αm, the Hamming code Hm beats projection.
- For m > 6, fm(m/2^m) < 0, providing the stated upper-side bound on the crossover analysis.
D. Other Linear Codes
The paper evaluates minimum-length binary linear codes using complete decoding algorithms to extend hashing strategies beyond the previously considered codes. The results show that performance depends on more than minimum code length.
- Complete decoding algorithms map every vector to a codeword, and translation invariance reduces comparison to the set decoding to zero.
- For each dimension and minimum distance, the experiments test a minimum-length [n, k, d] binary linear code.
- The [23, 12, 7] Golay code and Hamming codes H4 and H5 perform well among the tested codes.
- Concatenating Golay or Hamming codes with projection can outperform selected minimum-length codes, showing that factors beyond minimum length affect hashing-code quality.
III. OPTIMAL SETS
Finding an optimal set of a given size in the n-cube is a difficult problem with independent interest. The paper solves the problem for sizes up to 2^6 and examines the high-error-probability regime.
- Determining optimal sets S ⊂ F_2^n is independently interesting after studying sets associated with error-correcting codes.
- The general problem asks for an optimal set of size 2^t in V for an error probability p.
- The paper finds the answer for t ≤ 6 and studies behavior when p is near 1/2.
A. Optimal Sets of Small Size
For small optimal sets in the n-cube, structural transformations reduce the search to right-shifted down-sets. The paper enumerates these sets through size 2^6 and compares some with code-based constructions.
- Isomorphic sets have identical collision objective values PS(p) for every p ∈ [0, 1].
- An optimal set is isomorphic to a right-shifted down-set.
- By Theorem 9, all optimal sets can be found by examining right-shifted down-sets, which correspond to ideals in a poset.
- Computing all right-shifted down-sets of size 2^t for t ≤ 6 yields the listed optimal sets.
- Some optimal sets for t = 6 outperform the sets corresponding to the codes in Figure 1.
B. Optimal Sets for Large Error Probabilities
As p approaches 1/2, hashing-optimal sets are characterized through minimum distance-sum, with generalized 1-spheres optimal in a broad high-dimensional regime.
- As p →1/2−, an optimal set must minimize the distance-sum of S.
- Distance-sum optimality asks whether a set of size s achieves the minimum distance sum f(s, n).
- The paper notes that identifying distance-sum optimal sets remains difficult, despite results for small s and n and for large n.
- For n ≥s−1, generalized 1-spheres are distance-sum optimal except when s ∈{4, 8}, where subcubes are optimal.
- For n ≥2^t−1, t ≥4, a (2^t−1)-dimensional 1-sphere is hashing optimal when p is sufficiently close to 1/2.
IV. HASHES FROM RANDOM CODES
This section compares random-code hashing with k-bit projection through error exponents. Under the stated entropy condition, random codes achieve a strictly larger exponent and hence higher expected collision probability.
- Random codes under minimum weight decoding are analyzed as alternatives to projection, with code rate R = k/n.
- The paper also states that, for any p > 0, codes with rate R ≈1 can beat projection.
- If H(δ) < 1−R, a vector in a radius-d sphere around a codeword is decoded to that codeword with high probability.
- Theorem 14 gives EPn,k(p)−ER(p) ≥D(p, δ, ε) under ε ≤1/2, H(δ)<1−R, and ε≤2δ.
- D(p, δ, εmax) > 0 for every δ, p ∈(0, 1/2), so the random-code exponent exceeds the projection exponent.
- For p ∈(0,1/2), R ∈(0,1), and sufficiently large n, random codes have higher expected collision probability than projection.
APPENDIX
The appendix develops an efficient enumeration of right-shifted down-sets and reports computed optimal sets, crossover ranges, and cases where multiple nonisomorphic sets are optimal.
- By Theorem 9, optimal sets can be found by examining right-shifted down-sets, which correspond to poset ideals.
- GenIdeal enumerates poset ideals by recursively including or excluding the elements below a selected element.
- Precomputed incidence matrices reduce preprocessing to O(|P|^2), while the per-ideal time is O(|P|), or O(lg |P|) with a suitable element choice.
- The computation restricts enumeration to right-shifted down-sets whose size does not exceed the target.
- Size-32 sets took just over one second, whereas size-64 sets took 23 minutes on one processor.
- For (t,n)=(4,13), the 4-dimensional cube is optimal for p∈(0,0.3929), while another down-set is optimal for p∈(0.3929,0.5).
- Some parameter choices have more than two nonisomorphic optimal down-sets, and some such sets share the same distance distribution.