Andoni, A., Laarhoven, T., Razenshteyn, I. and Waingarten, E. (2017). Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proc. SODA 2017, pp. 47–66. DOI 10.1137/1.9781611974782.4
Key takeaways
Read in full (NOTE-918). For c-approximate near-neighbour search (find a point within cr when one lies within r) over n points in Euclidean space, the paper gives a data structure for every pair of exponents with c²√ρq + (c²−1)√ρu ≥ √(2c²−1), using space n^{1+ρu+o(1)} + O(dn) and query time n^{ρq+o(1)} + dn^{o(1)}, on worst-case data (for Hamming and ℓ_1, c√ρq + (c−1)√ρu ≥ √(2c−1)). It proves the curve cannot be beaten by list-of-points structures, the model of all known data-independent hashing schemes, on random instances, and unconditionally in the cell-probe model only at one end (query n^{o(1)}) for one or two probes. So the exact trade between space spent organizing and per-query time is known within the hashing model; outside that model, for more than two probes, it is not, and data-dependent schemes are covered only by conjecture.
Why this is here
QUESTION-114 and THEORY-340 (Yao 1981): the exact trade-off curve between space spent organizing and query time for hashing-based approximate similarity search. Its lower bounds hold on random instances in the list-of-points model, and unconditionally only for one or two probes.