Source
Indyk and Motwani (1998), LIT-1106, STOC 1998 pp. 604–613, read in NOTE-905 from the authors’ “preliminary version” of December 30, 1999 (Indyk’s MIT directory), with every statement compared against the STOC text. Theorem numbers are the 1999 text’s.
What was actually shown
The problem and the cost model. Given n points in a metric space, answer a query q with a point within (1+ε) times the nearest distance, or, in the decision version (ε-PLEB), say whether some point lies within r or none within (1+ε)r. The algorithms are randomized and succeed with constant probability per query, for every data set and query. “Throughout, preprocessing cost refers to the space requirement; typically, the preprocessing time is roughly the same.”
The LSH theorem (Theorem 5). If a family H is (r1, r2, p1, p2)-sensitive (near pairs collide with probability at least p1, far pairs at most p2), then concatenating k = log_{1/p2} n functions per table and keeping l = n^ρ tables answers (r1, r2)-PLEB in O(dn + n^{1+ρ}) space with O(n^ρ) hash evaluations, ρ = ln(1/p1)/ln(1/p2). Every point is stored in every table. Bit sampling is sensitive in Hamming space (Proposition 4), giving ρ ≤ 1/(1+ε) (Corollary 3); embeddings carry this to ℓ_p, p in [1, 2] (Proposition 1). Min-wise hashing does the same for set resemblance (Corollary 4).
The STOC text is weaker. It defines ρ = ln(1/p1)/ln(p1/p2), and states Proposition 1 and Corollary 3 “For ε > 1” with exponent 1/ε, so in the published version sublinear queries are claimed only for approximation factors above 2.
The other end (Propositions 2, 3). Storing every grid cell that meets a ball in a perfect hash table gives Õ(d) query time for n·O(1/ε)^d preprocessing, any ℓ_p; random projection first gives (nd)^{O(1)} preprocessing with an exponent growing in 1/ε.
From decision to search (Section 3). One PLEB structure per radius costs O(log R) space for R the spread of distances; ring-cover trees remove R, built in Õ(n²) time with O(log² n · log k) PLEB queries per search. Some proofs are sketches.
What could have come out otherwise. A sensitive family with the stated p1, p2 for which no choice of k and l reaches the stated bounds would refute Theorem 5; the analysis is a short calculation and has been reused since.
What this does not say
- That these exponents are the best possible, for hashing or for any structure. The paper proves no lower bound. That question is THEORY-372’s and THEORY-381’s.
- That organizing ahead pays after some number of queries. Costs are per query, worst case; there is no query sequence, workload or break-even, no build cost apart from space, and upkeep only in dynamic variants that need bounded integer coordinates.
- Anything about exact nearest neighbours, or about answers with higher than constant probability without extra copies.
- That one partition suffices. The construction needs n^ρ independent random partitions precisely because one separates near pairs too often.
Connections
- QUESTION-114: three points on the trade between space paid once and time per query for similarity search (n^{1+1/(1+ε)} against n^{1/(1+ε)}; n·O(1/ε)^d against Õ(d); linear space against a linear scan). It prices neither side’s minimum.
- CLAIM-310: the single-arrangement constraint is escaped by keeping many random partitions and storing every point in each, paid for in space; the partitions ignore the query mix.
- THEORY-340: the same convention that building is free, for similarity rather than membership; algorithms, not a lower bound.
- THEORY-372 extends this account to the full curve of space against query exponents and shows where it is optimal.