Lucene For Approximate Nearest-neighbors Search On Arbitrary Dense Vectors

Abstract

We demonstrate three approaches for adapting the open-source Lucene search library to perform approximate nearest-neighbor search on arbitrary dense vectors, using similarity search on word embeddings as a case study. At its core, Lucene is built around inverted indexes of a document collection's (sparse) term-document matrix, which is incompatible with the lower-dimensional dense vectors that are common in deep learning applications. We evaluate three techniques to overcome these challenges that can all be natively integrated into Lucene: the creation of documents populated with fake words, LSH applied to lexical realizations of dense vectors, and k-d trees coupled with dimensionality reduction. Experiments show that the "fake words" approach represents the best balance between effectiveness and efficiency. These techniques are integrated into the Anserini open-source toolkit and made available to the community.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyteofili2019lucene

Related papers

• Efficient And Effective Retrieval Of Dense-sparse Hybrid Vectors Using Graph-based Approximate Nearest Neighbor Search (2024)0.00
• End-to-end Retrieval With Learned Dense And Sparse Representations Using Lucene (2023)0.00
• Dimensionality-reduction Techniques For Approximate Nearest Neighbor Search: A Survey And Evaluation (2024)0.00
• Vectorsearch: Enhancing Document Retrieval With Semantic Embeddings And Optimized Search (2024)0.00
• Semantic Vector Encoding And Similarity Search Using Fulltext Search Engines (2017)6.77
• Leanvec: Searching Vectors Faster By Making Them Fit (2023)0.00
• Gleanvec: Accelerating Vector Search With Minimalist Nonlinear Dimensionality Reduction (2024)0.00
• Associative Memories To Accelerate Approximate Nearest Neighbor Search (2016)6.34