Yang, KaixiangWang, HongyaDu, MingWang, ZhizhengTan, ZongyuanXiao, YingyuanLee, Sung-Hee and Zollmann, Stefanie and Okabe, Makoto and Wünsche, Burkhard2021-10-142021-10-142021978-3-03868-162-5https://doi.org/10.2312/pg.20211397https://diglib.eg.org:443/handle/10.2312/pg20211397Similarity search is an indispensable component in many computer vision applications. To index billions of images on a single commodity server, Douze et al. introduced L&C that works on operating points considering 64-128 bytes per vector. While the idea is inspiring, we observe that L&C still suffers the accuracy saturation problem, which it is aimed to solve. To this end, we propose a simple yet effective two-layer graph index structure, together with dual residual encoding, to attain higher accuracy. Particularly, we partition vectors into multiple clusters and build the top-layer graph using the corresponding centroids. For each cluster, a subgraph is created with compact codes of the first-level vector residuals. Such an index structure provides better graph search precision as well as saves quite a few bytes for compression. We employ the second-level residual quantization to re-rank the candidates obtained through graph traversal, which is more efficient than regression-from-neighbors adopted by L&C. Comprehensive experiments show that our proposal obtains over 30% higher recall@1 than the state-of-thearts, and achieves up to 7.7x and 6.1x speedup over L&C on Deep1B and Sift1B, respectively.Information systemsTopk retrieval in databases10.2312/pg.2021139781-86