The composed data structure of §7.4: the machine part of Theorem 1.1
OpenDetANN.Thm11.outer_compositionapproximate-nearest-neighborprogram-verificationreal-ram
Let be deterministic programs, and let and be such that the pair has the guarantees of Lemma 3.3. That is, for all , every injective and every , it is a deterministic -ANN structure for with:
- preprocessing time ;
- space ;
- query time .
Let . Then there are deterministic programs and constants with the following property. For every instance (, injective , ) there are with and such that:
- preprocessing (input parameter ) halts within steps and stores to at most that many cells;
- every query is answered within steps;
- every answer satisfies (definition
DetANN_Thm11_Split). That is, some candidates , one per walk tuple , satisfy the local guarantee (25) with for the blocks and the tuples , and for all .
This is the construction of §7.4. Pad to and build the greedy blocks of Theorem 3.2 with . For each , preprocess the superblock projections (dimension ) with a relocated copy of in its own memory window. A query runs a relocated in each window and returns the best of the candidates.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_DetANN_Construction import Definitions.Def_DetANN_TupleFamily import Definitions.Def_DetANN_Thm11_Split
Formal statement
namespace DetANN
namespace Thm11
/-- **The composed data structure of §7.4 (machine part of Theorem 1.1).** Given any deterministic
pair `Pre₃, Qry₃` with the guarantees of Lemma 3.3 (constants `C > 1`, `K`, `C'`) and any `C₀s > 0`,
there are deterministic outer programs and constants `Cm, Km` such that for every instance
(`1 ≤ d ≤ n`, injective `P`, `ε ∈ (0, 1)`) there are a padding exponent `k` with `d ≤ 2^k` and a
`C₀ ≥ C₀s` for which preprocessing halts within `Cm·n^{Km·ε^{−Km}}` steps and stores to at most
that many cells, and every query is answered within `Cm·(d² + d·ε^{−Km}(1 + log n)^{Km})` steps by
an index that is at least as close to `q` as some family of candidates satisfying the local
guarantee (25) with `α = 1 + ε/100` for `annBlocks C₀ k P ε` and `annTuples k ε`. -/
theorem outer_composition :
∀ (Pre₃ Qry₃ : PNormReg.Program), DetProgram Pre₃ → DetProgram Qry₃ →
∀ (C : ℝ) (K C' : ℕ), 1 < C →
(∀ m N : ℕ, 1 ≤ m → 1 ≤ N →
∀ Y : Fin N → EuclideanSpace ℝ (Fin m), Function.Injective Y →
∀ δ : ℝ, 0 < δ → δ < 1 / 2 →
IsDetANNStructure Pre₃ Qry₃ Y δ (1 + δ)
((C' : ℝ) * ((N : ℝ) + m) ^ K * (C / δ) ^ ((K : ℝ) * m) * Real.log (N / δ) ^ K)
((C' : ℝ) * N * (C / δ) ^ ((K : ℝ) * m) * Real.log (N / δ) ^ K)
((C' : ℝ) * (m : ℝ) ^ 2 * Real.log (N / δ) ^ 2)) →
∀ C₀s : ℝ, 0 < C₀s →
∃ Pre Qry : PNormReg.Program, DetProgram Pre ∧ DetProgram Qry ∧
∃ Cm Km : ℕ, ∀ d n : ℕ, 1 ≤ d → d ≤ n →
∀ P : Fin n → EuclideanSpace ℝ (Fin d), Function.Injective P →
∀ ε : ℝ, 0 < ε → ε < 1 →
∃ (k : ℕ) (C₀ : ℝ), d ≤ 2 ^ k ∧ C₀s ≤ C₀ ∧
IsDetStructure Pre Qry P ε (LocalAnswer C₀ k P ε)
((Cm : ℝ) * (n : ℝ) ^ ((Km : ℝ) * ε⁻¹ ^ Km))
((Cm : ℝ) * (n : ℝ) ^ ((Km : ℝ) * ε⁻¹ ^ Km))
((Cm : ℝ) * ((d : ℝ) ^ 2 + d * ε⁻¹ ^ Km * (1 + Real.log n) ^ Km)) := by sorry
end Thm11
end DetANNSource
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as the top-level reduction of DetANN.theorem_1_1 (Feng, Indyk, STOC 2027 submission, Theorem 1.1, p.2; the construction of §7.4, p.19). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.