Query cost of the HPIM tree
ProvedDetANN.HPIM.hpimTree_costapproximate-nearest-neighborcomputational-geometrydata-structures
There is an absolute constant such that the following holds. Let , let be distinct, and . Then the search of (definition DetANN_HPIMTree) has cost
The tree has at most levels, because each recursion at least halves the point set. Each level makes at most two lookups and one ladder search of probes, and each lookup visits nodes.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMTree
Formal statement
namespace DetANN.HPIM
/-- **Query cost of the HPIM tree.** 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 δ` visits at
most `C₁ m log²(N/δ)` nodes. -/
theorem hpimTree_cost :
∃ C₁ : ℕ, ∀ (m N : ℕ), 1 ≤ m → 1 ≤ N →
∀ Y : Fin N → EuclideanSpace ℝ (Fin m), Function.Injective Y →
∀ δ : ℝ, 0 < δ → δ < 1 / 2 → ∀ q : EuclideanSpace ℝ (Fin m),
((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.