Hierarchical Link and Code: Efficient Similarity Search for Billion-Scale Image Sets

Simple item page
dc.contributor.authorYang, Kaixiangen_US
dc.contributor.authorWang, Hongyaen_US
dc.contributor.authorDu, Mingen_US
dc.contributor.authorWang, Zhizhengen_US
dc.contributor.authorTan, Zongyuanen_US
dc.contributor.authorXiao, Yingyuanen_US
dc.contributor.editorLee, Sung-Hee and Zollmann, Stefanie and Okabe, Makoto and Wünsche, Burkharden_US
dc.date.accessioned2021-10-14T10:05:48Z
dc.date.available2021-10-14T10:05:48Z
dc.date.issued2021
dc.description.abstractSimilarity 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.en_US
dc.description.sectionheadersImage Processing and Synthesis
dc.description.seriesinformationPacific Graphics Short Papers, Posters, and Work-in-Progress Papers
dc.identifier.doi10.2312/pg.20211397
dc.identifier.isbn978-3-03868-162-5
dc.identifier.pages81-86
dc.identifier.urihttps://doi.org/10.2312/pg.20211397
dc.identifier.urihttps://diglib.eg.org:443/handle/10.2312/pg20211397
dc.publisherThe Eurographics Associationen_US
dc.subjectInformation systems
dc.subjectTop
dc.subjectk retrieval in databases
dc.titleHierarchical Link and Code: Efficient Similarity Search for Billion-Scale Image Setsen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
081-086.pdf
Size:
298.61 KB
Format:
Adobe Portable Document Format
Download
Collections
PG2021 Short Papers, Posters, and Work-in-Progress Papers