Can I read Range Retrieval with Graph-Based Indices on EtoBox?

Range Retrieval with Graph-Based Indices by Manohar, Magdalen Dobson; Kim, Taekseung; Blelloch, Guy E. is a scholarly article available to read on EtoBox.

What is Range Retrieval with Graph-Based Indices about?

Retrieving points based on proximity in a high-dimensional vector space is a crucial step in information retrieval applications. The approximate nearest neighbor search (ANNS) problem, which identifies the $k$ nearest neighbors for a query (approximately, since exactly is hard), has been extensively studied in recent years. However, comparatively little attention has been paid to the related problem of finding all points within a given distance of a query, the range retrieval problem, despite its applications in areas such as duplicate detection, plagiarism checking, and facial recognition. In this paper, we present a set of algorithms for range retrieval on graph-based vector indices, which are known to achieve excellent performance on ANNS queries. Since a range query may have anywhere from no matching results to thousands of matching results in the database, we introduce a set of range retrieval algorithms based on modifications of the standard graph search that adapt to terminate quickly on queries in the former group, and to put more resources into finding results for the latter group. Due to the lack of existing benchmarks for range retrieval, we also undertake a comprehensiv

Author

Manohar, Magdalen Dobson; Kim, Taekseung; Blelloch, Guy E.

Published

2025

Language

EN