PG2021 Short Papers, Posters, and Work-in-Progress Papers

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/2633094

Browse

Browsing PG2021 Short Papers, Posters, and Work-in-Progress Papers by Subject "k retrieval in databases"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Hierarchical Link and Code: Efficient Similarity Search for Billion-Scale Image Sets
    (The Eurographics Association, 2021) Yang, Kaixiang; Wang, Hongya; Du, Ming; Wang, Zhizheng; Tan, Zongyuan; Xiao, Yingyuan; Lee, Sung-Hee and Zollmann, Stefanie and Okabe, Makoto and Wünsche, Burkhard
    Similarity 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.