The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
Abstract
Large-scale information retrieval systems, including retrieval-augmented generation (RAG) and recommendation engines, widely use multi-layered hierarchical data structures for ultra-fast approximate nearest-neighbor search in high-dimensional vector spaces. However, the geometric conditions that ensure accurate and efficient greedy navigation remain poorly understood. In this work, we study the efficiency of greedy navigation on a hierarchy of proximity graphs constructed from n data points on the d-dimensional torus~πd. We identify a deterministic coverage condition under which, given any query qβ πd, greedy search returns a point within (1+Ξ΅)-factor of the distance to the closest point. This coverage property holds with high probability when the data is distributed as a homogeneous Poisson process, a Hermitian determinantal process, or a bounded-density Cox process, as long as d = o(log n/log log n). Under the same assumptions, the expected number of greedy hops for a fixed query is O (exp (1/2 dlog d+O(d))log n), yielding logarithmic expected hop count in fixed dimension.
Related
- SN-ASMO: Satellite-Navigation Array Spatial-Manifold Precise Observation Theory A Mathematical Foundation for Observation Formation, Unified U(1) Geometry, Intrinsic Information, and Preservation of the RTK Integer Structure
- Small-study effects on the hierarchical summary ROC curve: latent accuracy and threshold trends in meta-analysis of diagnostic test accuracy
- Modeling Transition Dynamics and Network Structure in Cross-National Process Data: A Hierarchical Multi-State Survival Framework
- Hierarchical geometry and right-angled Artin groups in graph braid groups
- Reconstruction of Heat Geometry from a Scalar Process
BibTeX
@misc{bhamidi2026geometry,
title = {{The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input}},
author = {Shankar Bhamidi and Souvik Dhara and Lars Schroeder and Clara Stegehuis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12312},
eprint = {2610.12312},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12312},
}
RIS
TY - UNPB
TI - The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
AU - Shankar Bhamidi
AU - Souvik Dhara
AU - Lars Schroeder
AU - Clara Stegehuis
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12312
UR - https://arxiv.org/abs/2610.12312
AB - Large-scale information retrieval systems, including retrieval-augmented generation (RAG) and recommendation engines, widely use multi-layered hierarchical data structures for ultra-fast approximate nearest-neighbor search in high-dimensional vector spaces. However, the geometric conditions that ensure accurate and efficient greedy navigation remain poorly understood. In this work, we study the efficiency of greedy navigation on a hierarchy of proximity graphs constructed from n data points on the d-dimensional torus~π^d. We identify a deterministic coverage condition under which, given any query qβ π^d, greedy search returns a point within (1+Ξ΅)-factor of the distance to the closest point. This coverage property holds with high probability when the data is distributed as a homogeneous Poisson process, a Hermitian determinantal process, or a bounded-density Cox process, as long as d = o(log n/log log n). Under the same assumptions, the expected number of greedy hops for a fixed query is O (exp (1/2 dlog d+O(d))log n), yielding logarithmic expected hop count in fixed dimension.
ER -