The query program for well-formed HPIM trees
ProvedDetANN.HPIM.hpim_query_program_wfapproximate-nearest-neighborcomputational-geometrydata-structures
There are a deterministic PNormReg program and a constant such that the following holds. Let , and let be a well-formed HPIM tree (definition DetANN_HPIMWF). 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
This corrects DetANN.HPIM.hpim_query_program, which omits well-formedness and is false: the layout does not store the number of local points, so one memory can store two trees that differ only in and that have different search results.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_DetANN_HPIMLayout import Definitions.Def_DetANN_HPIMWF
Formal statement
namespace DetANN.HPIM
/-- **The query program** (for well-formed trees). One deterministic PNormReg program reads any
well-formed 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_wf :
∃ Qry : PNormReg.Program, DetProgram Qry ∧ ∃ c₀ : ℕ,
∀ (m : ℕ) (s : PNormReg.State) (T : HTree m) (q : EuclideanSpace ℝ (Fin m)),
1 ≤ m → T.WF → 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). It corrects DetANN.HPIM.hpim_query_program, which is false because the layout does not store the number of local points.