The HPIM tree is a (1+δ)-ANN structure
ProvedDetANN.HPIM.hpim_tree_correctapproximate-nearest-neighborcomputational-geometrydata-structures
There is an absolute constant such that the following holds. Let , let be distinct, and . The search of (definition DetANN_HPIMTree) returns an index with
and its cost is at most .
This is the mathematical content of DetANN.lemma_3_3. The remaining steps are the two machine programs: one builds the tree in memory, and one runs this search.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMTree
Formal statement
namespace DetANN.HPIM
/-- **The HPIM tree is a `(1+δ)`-ANN structure with query cost `O(m log²(N/δ))`.** There is an absolute
constant `C₁` such that for `m ≥ 1`, `N ≥ 1` distinct points `Y ⊆ ℝ^m`, `δ ∈ (0, 1/2)` and every query
`q`, the search of `hpimTree Y δ` returns an index `k` with `‖q − Y_k‖ ≤ (1 + δ) ‖q − Y_j‖` for all
`j`, and visits at most `C₁ m log²(N/δ)` nodes. -/
theorem hpim_tree_correct :
∃ C₁ : ℕ, ∀ (m N : ℕ), 1 ≤ m → 1 ≤ N →
∀ Y : Fin N → EuclideanSpace ℝ (Fin m), Function.Injective Y →
∀ δ : ℝ, 0 < δ → δ < 1 / 2 → ∀ q : EuclideanSpace ℝ (Fin m),
(∃ k : Fin N, (hpimTree Y δ).search q = k ∧ ∀ j : Fin N, ‖q - Y k‖ ≤ (1 + δ) * ‖q - Y j‖) ∧
((hpimTree Y δ).cost q : ℝ) ≤ C₁ * m * Real.log (N / δ) ^ 2 := 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.