LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table
Approximate nearest neighbor search (ANNS) is an essential building block for applications like RAG but can sometimes yield results that are overly similar to each other. In certain scenarios, search results should be similar to the query and yet diverse. We propose LotusFilter, a post-processing module to diversify ANNS results. We precompute a cutoff table summarizing vectors that are close to each other. During the filtering, LotusFilter greedily looks up the table to delete redundant vectors from the candidates. We demonstrated that the LotusFilter operates fast (0.02 [ms/query]) in settings resembling real-world RAG applications, utilizing features such as OpenAI embeddings. Our code is publicly available at https://github.com/matsui528/lotf.
Code (1)
Tasks
RAGMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fast Nearest Neighbor Machine Translation
Though nearest neighbor Machine Translation ($k$NN-MT) \citep{khandelwal2020nearest} has proved to introduce significant performance boosts over standard neural MT systems, it is prohibitively slow since it uses the enti…
Machine TranslationNMTSentenceTranslationEFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph
Approximate nearest neighbor (ANN) search is a fundamental problem in many areas of data mining, machine learning and computer vision. The performance of traditional hierarchical structure (tree) based methods decreases …
graph constructionFast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs
We explore the use of GPU for accelerating large scale nearest neighbor search and we propose a fast vector-quantization-based exhaustive nearest neighbor search algorithm that can achieve high accuracy without any index…
GPUQuantizationTensor-Train Point Cloud Compression and Efficient Approximate Nearest-Neighbor Search
Nearest-neighbor search in large vector databases is crucial for various machine learning applications. This paper introduces a novel method using tensor-train (TT) low-rank tensor decomposition to efficiently represent …
Density EstimationOut of Distribution (OOD) DetectionTensor DecompositionLearning Representations for Faster Similarity Search
In high dimensions, the performance of nearest neighbor algorithms depends crucially on structure in the data. While traditional nearest neighbor datasets consisted mostly of hand-crafted feature vectors, an increasing n…
General Classification