arXiv preprint ·
The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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~$\mathbb{T}^d$. We identify a deterministic coverage condition under which, given any query $q\in \mathbb{T}^d$, greedy search returns a point within $(1+\varepsilon)$-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\!\left(\exp\!\left(\tfrac12 d\log d+O(d)\right)\log n\right)\), yielding logarithmic expected hop count in fixed dimension.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Ellipsoids from Tangents
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges
Deterministic Distance Selection in $O(n^{4/3})$ Time
Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.