In this paper, we compare the performances of FAISS and FENSHSES on nearest neighbor search in Hamming space-a fundamental task with ubiquitous applications in nowadays eCommerce. Comprehensive evaluations are made in terms of indexing speed, search latency and RAM consumption. This comparison is conducted towards a better understanding on trade-ofs between nearest neighbor search systems implemented in main memory and the ones implemented in secondary memory, which is largely unaddressed in literature.
• Information systems → Nearest-neighbor search; Image search; • Applied computing → Online shopping; • Software and its engineering → Memory management;
Nearest neighbor search (NNS) within semantic embeddings (a.k.a.,
vector similarity search) has become a common practice in
ubiquitous eCommerce applications including neural ranking model
based text search [
NNS solutions implemented in secondary memory. In contrast, the
second type of NNS solutions are delivered only recently by active
eforts from both academia and industry [
In this paper, we will shed light on the above questions through a
case study on the task of nearest neighbor search in Hamming space
(i.e., the space of binary codes). This task is an extremely important
subclass of NNS, as learning and representing textual, visual and
acoustic data with compact and semantic binary vectors is a pretty
mature technology and common practice in nowadays IR systems.
In particular, eBay recently builds its whole visual search system
[
We choose one representative solution of each category–FAISS
(Facebook AI Similarity Search) from Facebook’s AI Research Lab
[
Data generation. Our dataset B is generated using 2.8 million
images selected from Walmart.com’s home catalog through pHash
[
Settings. For FAISS, we use its binary flat index with five threads. For a fair comparison, we accordingly deploy FENSHSES by creating its Elasticsearch index with five shards and zero replica. The rest of configurations are left as their default and suggested values. Both FAISS and FENSHSES are set up and tested on the same Microsoft Azure virtual machine.
Speed in indexing. During the indexing phase, FAISS indexes the data into main memory (i.e., RAM), while FENSHSES indexes the data into secondary memory (e.g., hard disk). As a consequence, FAISS is much faster than FENSHSES in terms of data indexing (see Table 1). But on the other hand, whenever the process is killed and needs a restart, FAISS has to go through this procedure again to re-index data into RAM, while FENSHSES could unafectedly use its built index on hard disk without re-indexing.
# of Bits F(sAeIcS.)S FEN(sSeHc.)SES 64 18.5 75.5 256 37.7 140.2 1024 111.9 369.5 4096 397.3 1300.9 Table 1: Indexing time consumption. FAISS is about four times faster than FENSHSES in creating the index for nearest neighbor search.
Search latency. We randomly select 10, 000 binary codes from B to act as query codes. For each query code q, we instruct FAISS and FENSHSES to find all r -neighbors of q in B, namely
BH (q, r ) := {b ∈ B | dH (b, q) ≤ r } , (2.1) where dH (b, q) := Ími=1 1{bi ,qi } denotes the Hamming distance between binary code b and q, and the Hamming radius r ≥ 0. As shown in Table 2, FENSHSES is quite competitive for small radium r . This is because FENSHSES fully leverages Elasticsearch’s inverted index to first conduct a sub-code filtering to only consider a subset of B for Hamming distance computation, which is most efective for small r . In contrast, FAISS scans every binary code in B, so its search latency is almost invariant with respect to r . For applications (e.g., near-duplicate image detection and visual search) where we care most about nearest neighbors within a small radius, FENSHSES could be in a more favorable position than FAISS.
RAM consumption. Since FAISS is implemented in main memory, its RAM consumption undoubtedly rises along with the increase in the size of dataset B, as shown in Table 3. In contrast, by leveraging the highly optimized disk-based index mechanics behind full-text search engines, FENSHSES consumes a much smaller amount of RAM when conducting nearest neighbor search. This property makes FENSHSES more cost-efective and thus more suitable especially to big-data applications. In this case study, we compare FAISS and FENSHSES for the task of nearest neighbor search in Hamming space. By evaluating their performances in terms of speed in data indexing, search latency and RAM consumption, we hope practitioners could now better understand the pros and cons of the main memory based NNS solutions and the secondary memory based ones, and thus make their best choices accordingly (at least in NNS systems within binary cods). In the future, we will compare FAISS and FENSHSES under a wider range of applications; and moreover, we will also go beyond Hamming space to evaluate vector similarity search systems for general NNS problems.
We are grateful to three anonymous reviewers for their helpful suggestions and comments that substantially improve the paper. CM would like to thank Jun Zhao and Guang Yang for insightful discussions on FENSHSES. BY would like to thank Alessandro Magnani for helpful discussions on pHash and its related applications, and Zuzar Nafar for his support on this study.