Hierarchical search methods improve accuracy and speed in high dimensions
The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
Data Structures and AlgorithmsComputational Geometry
Summary
Finding the closest point in a huge set quickly is important for search and recommendation systems. This paper shows that for certain realistic random data patterns, a step-by-step search method on a layered network structure finds near-best results efficiently. It gives a clear condition that guarantees the search is both accurate and fast, especially in moderately high dimensions. These findings help explain why hierarchical searching works well in practice.
What this means in practice
- •For data engineers: Improve large-scale vector search by knowing when hierarchical graphs guarantee fast near-neighbor queries.
- •For recommendation system developers: Design faster recommendation engines that use layered search structures achieving rigorously bounded query hops and accuracy.
A theory result. No direct application yet.
Authors
Shankar Bhamidi, Souvik Dhara, Lars Schroeder, Clara Stegehuis
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.