Geo-filtered nearest neighbor search speeds location-based queries
Geo-Filtered Approximate Nearest-Neighbor Search on a Single Proximity Graph
Databases
Summary
Searching for nearby items that closely match a given feature is important for location-based services. Existing methods that filter by geographic area often slow down or lose accuracy. The authors introduce REACH, a new way to organize data in a single graph that maintains search speed and accuracy by carefully ordering neighbors. REACH works well even with very large datasets, making location-aware searches faster and more precise.
What this means in practice
- •For mobile app developers: Speed up location-based search features by efficiently retrieving nearby items with similar attributes in a single index structure.
- •For e-commerce platform engineers: Improve product search on maps by reducing search time and memory while keeping accurate nearby recommendations based on user location.
Authors
Zhiqiu Zou, Rong-Hua Li, Qiangqiang Dai, Guoren Wang
Abstract
Geo-filtered approximate nearest-neighbor (GFANN) search retrieves the objects inside a query-specified geographic disk whose feature vectors are closest to a query vector, a core operation in location-aware Web search. A disk filter on a standard proximity graph invalidates out-of-disk routing vertices; on selective disks, these removals break greedy paths and recall drops sharply. Existing methods scan all in-disk objects, over-fetch unfiltered candidates, or maintain separate sub-indexes across spatial partitions, trading latency for index overhead. We propose REACH, a single-graph index based on row-local active-order invariance: if every vertex stores its outgoing neighbors in a fixed-width row sorted by vector distance, any disk filter masks out-of-disk entries while surviving in-disk (active) neighbors remain vector-sorted. Offline, each vertex merges globally closest vector candidates with a nearest-first geographic stream into one row; online, beam search evaluates vector distances only for the first l active entries of each visited row. Because co-located objects share the same distance to every query center, every disk admits a coordinate group in full or not at all, decomposing active connectivity into intra-group and inter-coordinate conditions. Under a spatial marked-site model with repeated coordinates, we prove that polylogarithmic out-degree guarantees strong connectivity across all disks and constant-factor distance reduction per hop on compact disks, while a cut-rank threshold characterizes the minimum scan budget l. Across four datasets up to 10^7 objects, one REACH index per dataset outperforms SOTA methods, achieving 2.49x higher geometric-mean QPS than the strongest baseline at 0.95 Recall@10 on selective queries, while building 3.8x-11.9x faster and using 37%-45% less space than a SOTA spatial-graph index.