Range Retrieval with Graph-Based Indices
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 comprehensive study of range characteristics of existing embedding datasets, and select a suitable range retrieval radius for eight existing datasets with up to 100 million points in addition to the one existing benchmark. We test our algorithms on these datasets, and find up to 100x improvement in query throughput over a naive baseline approach, with 5-10x improvement on average, and strong performance up to 100 million data points.
Code (0)
등록된 구현이 없습니다.
Tasks
Information RetrievalRetrievalMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
Approximate nearest neighbor search (ANNS) is a fundamental building block in information retrieval with graph-based indices being the current state-of-the-art and widely used in the industry. Recent advances in graph-ba…
Information RetrievalRetrievalCubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data
Hybrid queries combining high-dimensional vector similarity search with spatio-temporal filters are increasingly critical for modern retrieval-augmented generation (RAG) systems. Existing systems typically handle these w…
Optimizing Component Combination in a Multi-Indexing Paragraph Retrieval System
We demonstrate a method to optimize the combination of distinct components in a paragraph retrieval system. Our system makes use of several indices, query generators and filters, each of them potentially contributing to …
Question AnsweringRetrievalOn Novel Approach for Computing Distance based Indices of Anti-tuberculosis Drugs
This work aims to assess the molecular architectures of anti-tuberculosis drugs using both degree-based topological indices and novel distance based indices. We can represent the chemical arrangement as a graph, with ato…
EnrichIndex: Using LLMs to Enrich Retrieval Indices Offline
Existing information retrieval systems excel in cases where the language of target documents closely matches that of the user query. However, real-world retrieval systems are often required to implicitly reason whether a…
Information RetrievalRetrieval