Fast And Exact Nearest Neighbor Search In Hamming Space On Full-text Search Engines

Abstract

A growing interest has been witnessed recently from both academia and industry in building nearest neighbor search (NNS) solutions on top of full-text search engines. Compared with other NNS systems, such solutions are capable of effectively reducing main memory consumption, coherently supporting multi-model search and being immediately ready for production deployment. In this paper, we continue the journey to explore specifically how to empower full-text search engines with fast and exact NNS in Hamming space (i.e., the set of binary codes). By revisiting three techniques (bit operation, subs-code filtering and data preprocessing with permutation) in information retrieval literature, we develop a novel engineering solution for full-text search engines to efficiently accomplish this special but important NNS task. In the experiment, we show that our proposed approach enables full-text search engines to achieve significant speed-ups over its state-of-the-art term match approach for NNS

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keymu2019fast

Related papers

• An Empirical Comparison Of FAISS And FENSHSES For Nearest Neighbor Search In Hamming Space (2019)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Learning To Hash Robustly, Guaranteed (2021)0.00
• Fast Search On Binary Codes By Weighted Hamming Distance (2020)0.00
• In-memory Nearest Neighbor Search With Fefet Multi-bit Content-addressable Memories (2020)11.85
• Bipartite Graph Convolutional Hashing For Effective And Efficient Top-n Search In Hamming Space (2023)8.82
• Fast And Exact Fixed-radius Neighbor Search Based On Sorting (2022)6.77
• Towards Effective Top-n Hamming Search Via Bipartite Graph Contrastive Hashing (2024)6.34