The lookup contract
ProvedDetANN.HPIM.lookupTree_specapproximate-nearest-neighborcomputational-geometrydata-structures
Let , let with , and . The lookup structure (definition DetANN_HPIMTree):
- satisfies the near-neighbour contract at radius and factor : an answer has , and a null answer means for all ;
- visits at most nodes at every query, where and .
This is the interface between the certified BSPs and the HPIM search. The visit bound is .
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMTree
Formal statement
namespace DetANN.HPIM
/-- **The lookup contract.** For `m ≥ 1`, `n ≥ 1` points `P_i ∈ ℝ^m`, `r > 0` and `δ ∈ (0, 1/2)`, the
lookup structure `lookupTree P r (1 + δ/4) δ` satisfies the near-neighbour contract at radius `r` and
factor `1 + δ/4`, and visits at most `5 ⌊log₂(2 · bspFuel n m δ)⌋ + 7` nodes at every query. -/
theorem lookupTree_spec {m : ℕ} (hm : 1 ≤ m) {n : ℕ} (hn : 1 ≤ n)
(P : Fin n → EuclideanSpace ℝ (Fin m)) (r δ : ℝ) (hr : 0 < r) (hδ : 0 < δ) (hδ' : δ < 1 / 2) :
NearNbrSpec P r (1 + δ / 4) (lookupTree (fun i j => P i j) r (1 + δ / 4) δ) ∧
∀ q : Fin m → ℝ, (lookupTree (fun i j => P i j) r (1 + δ / 4) δ).visits q ≤
5 * Nat.log 2 (2 * bspFuel n m δ) + 7 := by sorry
end DetANN.HPIMSource
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a floor-free proof of DetANN.lemma_3_3 (Feng, Indyk, STOC 2027 submission, Lemma 3.3, p.7). The search tree follows Har-Peled, Indyk, Motwani, Approximate nearest neighbor: towards removing the curse of dimensionality, Theory of Computing 8 (2012), §2, made deterministic and floor-free.