nucleation

THEORY-372: For c-approximate near-neighbour search over n points in Euclidean space, space n^{1+ρu+o(1)} and query time n^{ρq+o(1)} are achievable on any data set whenever c²√ρq + (c²−1)√ρu ≥ √(2c²−1) (c√ρq + (c−1)√ρu ≥ √(2c−1) in Hamming space), and no list-of-points structure, the model of known data-independent hashing, does better on random instances; without that model the curve is matched only at query time n^{o(1)} by one or two cell probes

4 min read

Properties7
StatusActive
Tagsdatabases, information-retrieval, mathematics
SourceLIT-1120 — Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
ExtendsTHEORY-388 — Locality-sensitive hashing answers approximate near-neighbour queries over n points with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, where ρ = ln(1/p1)/ln(1/p2) is set by how much more often near pairs collide than far ones and is at most 1/(1+ε) for approximation 1+ε in Hamming space, with constant success probability per query; the paper gives upper bounds only and proves no limit on what organizing can buy
PresupposesTHEORY-381 — In the cell-probe model, a near-neighbour structure on n random points that answers in t probes with m cells of w bits must satisfy m^t·w/n ≥ the robust expansion of the metric's neighbourhood graph at measure 1/m^t (and (mwt/n)^t ≥ its vertex expansion if deterministic), so in expanding spaces such as the hypercube fast queries need space polynomially larger than the data; the bounds are average case, approximate, and fall off exponentially in t
Bears onQUESTION-114 — Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks?
SupportsCLAIM-310 — Sorting schemes over objects with determinate properties never conflict as descriptions, since the product of any sortings refines them all; they conflict as arrangements, since a fixed number of bins realizes one partition when each item is stored once, and which costs least depends on what is searched for and on what stands out within a bin, CLAIM-313 — A fixed number of bins realizes one partition only when each item is stored once: with copies, overlapping partitions coexist, as hashing-based similarity search stores each item in many partitions and pays for it in space, so sortings conflict as arrangements only under a one-copy constraint, which binds bricks but not index entries

Graph View

Source

Andoni, Laarhoven, Razenshteyn and Waingarten (2017), LIT-1120, SODA 2017, read in NOTE-918 from arXiv:1608.03580v2, the full version merging the two preprints behind the extended abstract.

What was actually shown

The problem. (c, r)-ANN, c > 1: given that some point lies within r of the query, return a point within cr. Randomized structures, success probability at least 0.9 per query, expected space and time.

Upper bound (Theorem 1.1). For every ρq, ρu ≥ 0 with c²√ρq + (c² − 1)√ρu ≥ √(2c² − 1), a structure for any data set in ℝ^d has space n^{1+ρu+o(1)} + O(dn) and query time n^{ρq+o(1)} + dn^{o(1)}. Points are filed under every Gaussian cap of threshold ηu they fall in, queries look in every cap of threshold ηq they fall in, and dense clusters are removed and recursed on so that what remains looks random. Endpoints: query n^{o(1)} with space n^{c⁴/(c²−1)²}; near-linear space with query n^{(2c²−1)/c⁴}, sublinear for every c > 1; ρq = ρu = 1/(2c²−1). For c = 2: n^{1.77} with n^{o(1)}, n^{1.14} with n^{0.14}, n^{1+o(1)} with n^{0.43}. By cited reductions, c² becomes c^p for ℓ_p, 1 ≤ p < 2. Updates cost dn

Lower bound in the hashing model (Theorem 1.6). A list-of-points structure fixes sets A_i independently of the data, keeps L_i = P ∩ A_i, and has a query scan the lists in I(q); space counts list entries and time counts entries scanned. On random Hamming instances (uniform points, d = ω(log n), query a noisy copy of a data point), any such structure with space n^{1+ρu}, query time n^{ρq−o(1)} and success 2/3 satisfies c√ρq + (c − 1)√ρu ≥ √(2c − 1). The paper says it captures “all hashing-based frameworks we are aware of”, but not data-dependent ones, including its own upper bound.

Unconditional bounds at one end (Theorems 1.3, 1.4). In the cell-probe model, one probe with cells of n^{o(1)} bits, or two probes with cells of o(log n) bits, need n^{(c/(c−1))²−o(1)} words on the random instance: the curve’s space at ρq = 0. The one-probe bound applies the robust-expansion framework of THEORY-381 with a tight expansion estimate; the two-probe bound goes through locally decodable codes. “Informally speaking, Theorem 1.4 shows that the second cell probe cannot improve the space bound by more than a subpolynomial factor.”

What could have come out otherwise. A list-of-points scheme beating the curve on random instances, or a one-probe structure with fewer words, would refute the theorems; and the upper bound could have needed worse exponents on worst-case data than on random data, as the data-independent scheme alone does ((c² + 1)√ρq + (c² − 1)√ρu ≥ 2c, Theorem 1.2).

What this does not say

  • That the curve is optimal for every data structure. It is shown for list-of-points structures and, at ρq = 0, for one or two probes. The paper: “proving similar lower bounds unconditionally is far beyond the current reach of techniques.” Data-dependent schemes are covered by conjecture.
  • That it holds in low dimension. The lower bounds need d = ω(log n); the case d = Θ(log n) is open.
  • That real collections cost this much. The hard inputs are random. A data-dependent scheme may do better on data with structure; the bound does not say how much.
  • Anything about exact nearest neighbours, ranking, or query distributions.
  • An amortized or workload-based cost model. Costs are per query for a fixed data set. The paper’s one amortized remark is that n queries cost n^{1+ρu} + n^{1+ρq} “(implying that the balanced, LSH regime is most relevant)”. Build time is taken as near-linear in space, and upkeep enters only as dynamized update time.

Connections

  • QUESTION-114: for one problem, the exact price of organizing ahead against per-query cost, as replication (each point in about n^{ρu} lists) against lists scanned (about n^{ρq}). With Q queries the total is about n^{1+ρu} + Q·n^{ρq} (the record’s arithmetic), so the best point moves toward more organization as expected use grows. It is a part-answer: one query type, no workload, no staleness.
  • CLAIM-310: the lists may overlap, and at near-linear space query time is at least n^{(2c−1)/c²−o(1)} in Hamming space, so fast similarity search needs items filed in many bins. Nothing here bears on query mixes.
  • THEORY-340: the similarity analogue of a lookup floor, holding at one and two probes with arbitrary cell encoding, where Yao’s sorted-order optimality needed restricted cell contents.
  • THEORY-345: a different question (one structure for one query type, no index choice for a workload); no conflict.
  • Extends THEORY-388, whose bit-sampling LSH is a balanced (ρq = ρu) data-independent point, ρ = 1/c in Hamming space, above this curve’s 1/(2c−1); presupposes THEORY-381 for the one-probe bound.

Backlinks