The query program for HPIM trees
DisprovedDetANN.HPIM.hpim_query_programapproximate-nearest-neighborcomputational-geometrydata-structures
There are a deterministic PNormReg program and a constant such that the following holds. Let , let be any HPIM tree, and let be a state with that stores from (definition DetANN_HPIMLayout). On the query state for (definition DetANN_DataStructure), halts with the search result of at in pointer register , after work at most
Each node visit compares with a box, or reads an index, in steps. The ladder search reads the table of powers, so no pointer division is needed.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_DetANN_HPIMLayout
Formal statement
namespace DetANN.HPIM
/-- **The query program.** One deterministic PNormReg program reads any HPIM tree stored from
`I[2]` (with `I[1] = m`) in the layout of `DetANN_HPIMLayout`. On the query `q` it halts with the
search result in pointer register `0`, after work at most `c₀ (m + 1)` times the cost of the search. -/
theorem hpim_query_program :
∃ Qry : PNormReg.Program, DetProgram Qry ∧ ∃ c₀ : ℕ,
∀ (m : ℕ) (s : PNormReg.State) (T : HTree m) (q : EuclideanSpace ℝ (Fin m)),
1 ≤ m → s.integerMemory 1 = m → HTreeAt m s (s.integerMemory 2) T →
∃ t : ℕ,
(PNormReg.run Qry (queryState m s q) detTape t).halted = true ∧
(PNormReg.run Qry (queryState m s q) detTape t).work ≤ c₀ * (m + 1) * T.cost q ∧
(PNormReg.run Qry (queryState m s q) detTape t).core.ptrs 0 = T.search q := 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. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.