Lemma 5, p. 911 — the nearest neighbor search on a BBD-tree visits at most ⌈1 + 6d/ε⌉^d leaf cells, for any Minkowski metric
ProvedAryaANN.Search.lemma_5Let be a valid BBD-tree whose root cell is a box with no inner box, fix an distance on with ("any Minkowski metric"), an approximation parameter and a query point . Let be an enumeration of the leaf cells of such that
- every leaf cell occurs exactly once;
- the cells occur in nondecreasing order of distance from (ties in any order);
- the data point associated with lies in the outer box of .
The search processes in turn, keeping the closest point seen so far, and terminates at the first cell whose distance from exceeds . The number of cells visited up until termination, that is, the cells preceding the terminating cell, satisfies
The bound does not depend on the number of data points. Multiplied by the cost of enumerating each cell, it gives the query time of Theorem 1(i).
Formalization Note The paper's is a name for the number of visited cells; the formal conclusion is the explicit bound. A cell is processed (its point compared) before its own termination test, and counts the cells processed before the one whose test fires, or all of them if none fires. This is the count bounded in the paper's proof, where is the distance to "the last leaf cell that did not cause the algorithm to terminate" (p. 912). The printed statement says "the number of leaf cells visited"; if the firing cell is also counted, a valid one-dimensional tree with needs three processed cells against the bound , so the formal statement follows the proof's count (the discrepancy is recorded in HARD.md). The enumeration is a permutation of the leaf cells sorted by distance, the abstract output of property (e); the associated point lies in the cell's outer box, as in properties (a)–(b). The tree is any tree satisfying the §2.1 invariants, with any box as root. Theorem 1's time and space claims are not formalized.
import Mathlib import Definitions.Def_AryaANN_Search_Setting
namespace AryaANN.Search
/-- Lemma 5 (p. 911): the number `N` of leaf cells the search visits up until termination is at
most `⌈1 + 6d/ε⌉^d`. As in the proof (p. 912), `N` counts the cells that did not cause termination;
the cell whose test fires is not counted (counting it, the printed bound can be exceeded by one). -/
theorem lemma_5 {d : ℕ} (m : ℕ∞) (hm : 1 ≤ m) (C : Rect d) (T : BBDTree d)
(hT : Valid ⟨C, none⟩ T) (ε : ℝ) (hε : 0 < ε) (q : Fin d → ℝ)
(E : List (Cell d × (Fin d → ℝ)))
(hperm : (E.map Prod.fst).Perm (leaves ⟨C, none⟩ T))
(hpt : ∀ e ∈ E, e.2 ∈ e.1.outer.toSet)
(hsorted : E.Pairwise (fun a b => cellDist m q a.1 ≤ cellDist m q b.1))
(N : ℕ) (hN : IsVisitCount m ε q E N) :
N ≤ ⌈1 + 6 * (d : ℝ) / ε⌉₊ ^ d := by sorry
end AryaANN.Search
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.