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 within binary codes.
Introduction
Nearest Neighbor Search (NNS)—the process of finding items most similar to a query—is a cornerstone of modern recommendation systems and visual search. While specialized libraries like FAISS or Annoy provide high performance, they typically operate entirely in RAM, making them costly for massive datasets and difficult to integrate with traditional text-based metadata filters such as price or brand.
Full-text search engines like Elasticsearch are ideal for production because they are disk-based and handle multi-modal queries natively. However, they traditionally struggle with binary codes in Hamming space. The common approach of treating binary digits as text tokens is computationally expensive and ignores the mathematical properties of binary data. This research introduces a way to bridge this gap, making search engines as efficient for binary vectors as they are for text.
Methodology: The FENSHSES System
The proposed system, FENSHSES (Fast Exact Neighbor Search in Hamming Space on Elasticsearch), integrates three core techniques to optimize performance within the search engine framework:
- Native Bit Operations: Instead of string matching, the system implements the HAKMEM bit-counting algorithm using Elasticsearch’s "Painless" scripting language. This allows the engine to calculate Hamming distances using raw bitwise logic, providing an immediate 16x performance boost over standard term matching.
- Sub-code Filtering: To avoid exhaustive linear scans, the system uses a counting argument based on the pigeonhole principle. By splitting binary codes into segments, the engine can use its native inverted index to identify a small list of candidates that are mathematically guaranteed to contain the nearest neighbors, discarding over 99% of irrelevant results before heavy computation begins.
- Data Preprocessing with Permutation: Filtering efficiency depends on bit independence. The authors use the Kernighan-Lin algorithm to reorder (permute) bits before indexing, minimizing correlations within segments and ensuring consistent search latencies.
Experimental Setup and Results
The system was evaluated using a dataset of 500,000 images from the Jet.com furniture catalog. These images were converted into 128-bit and 256-bit binary vectors using a supervised semantic-preserving deep hashing (SSDH) model.
Performance gains were dramatic across all tests:
- Raw Speed: For 128-bit codes with a search radius of 5, FENSHSES achieved a latency of 1.08 ms, compared to 641.99 ms for the standard term-match approach—a ~600x speedup.
- Scalability: Even at 256 bits, the system remained highly efficient (2.18 ms vs 1259.22 ms).
- Stability: The permutation step significantly reduced the standard deviation of search latencies, providing a more predictable user experience.
Conclusion
FENSHSES demonstrates that full-text search engines can be empowered to perform fast, exact NNS in Hamming space without sacrificing their production-ready benefits. While the effectiveness of sub-code filtering diminishes as the search radius increases, the current implementation offers a massive leap forward for multi-modal production search systems. Future work may explore more advanced bit-permutation algorithms to further optimize bit grouping.
Summary updated