Towards Large-Scale Object Instance Search: A Multi-Block N-Ary Trie

被引:0
作者
Feng, Dong [1 ,2 ]
Liang, Man-Gui [1 ,2 ]
Gao, Feng [3 ]
Huang, Yi-Cheng [4 ]
Zhang, Xin-Feng [4 ]
Duan, Ling-Yu [4 ,5 ]
机构
[1] Beijing Jiaotong Univ, Inst Informat Sci, Beijing 100044, Peoples R China
[2] Beijing Jiaotong Univ, Beijing Key Lab AISNT, Beijing 100044, Peoples R China
[3] Tsinghua Univ, Future Lab, Beijing 100084, Peoples R China
[4] Peking Univ, Natl Engn Lab Video Technol, Beijing 100871, Peoples R China
[5] Peng Cheng Lab, Shenzhen 518066, Peoples R China
关键词
Veins; Binary codes; Search problems; Computational efficiency; Task analysis; Optimization; Indexing; Object search; binary code; indexing; hashing; exact nearest neighbor search; approximate nearest neighbor (ANN) search; QUANTIZATION; SPACE;
D O I
10.1109/TCSVT.2020.2966541
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Object instance search is a challenging task with a wide range of applications, but the fast search with high accuracy has not been well solved yet. In this paper, we investigate the object instance search from a new perspective in terms of joint precision and computational cost optimization, and propose a novel index structure i.e., Multi-Block N-ary Trie (MBNT) to accelerate the exact r-neighbor search in the Hamming space. Comprehensive studies are first carried out to reveal the performance of exact and approximate nearest neighbor (NN) algorithms for object instance search. An interesting finding that the exact search is more promising for very compact binary codes (e.g., 64-bit and 128-bit) is analyzed. Along this vein, we introduce a Trie structure, i.e., MBNT, which is specifically designed for improving the exact NN search performance in the context of large-scale object instance search. To index the binary codes, a subset of continuous bits of a binary string, denoted as a block, is regarded as an atomic indexing element. As such, the problem of lookup misses can be addressed. Theoretical analyses are also provided to show that our MBNT scheme can incur less computational cost than other hash table-based methods. Extensive experimental results on the 100M dataset have demonstrated that our method achieves faster search speed while maintaining the promising search precision towards large-scale object instance search.
引用
收藏
页码:372 / 386
页数:15
相关论文
共 59 条
[1]  
Andoni A, 2006, ANN IEEE SYMP FOUND, P459
[2]  
[Anonymous], 2013, SSDBM
[3]  
[Anonymous], 2016, P INT JOINT C ART IN
[4]  
[Anonymous], 2016, P INT C LEARNING REP
[5]   Neural Codes for Image Retrieval [J].
Babenko, Artem ;
Slesarev, Anton ;
Chigorin, Alexandr ;
Lempitsky, Victor .
COMPUTER VISION - ECCV 2014, PT I, 2014, 8689 :584-599
[6]   Correlational spectral clustering [J].
Blaschko, Matthew B. ;
Lampert, Christoph H. .
2008 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOLS 1-12, 2008, :93-+
[7]   Deep Visual-Semantic Quantization for Efficient Image Retrieval [J].
Cao, Yue ;
Long, Mingsheng ;
Wang, Jianmin ;
Liu, Shichen .
30TH IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR 2017), 2017, :916-925
[8]   HashNet: Deep Learning to Hash by Continuation [J].
Cao, Zhangjie ;
Long, Mingsheng ;
Wang, Jianmin ;
Yu, Philip S. .
2017 IEEE INTERNATIONAL CONFERENCE ON COMPUTER VISION (ICCV), 2017, :5609-5618
[9]   Total recall: Automatic query expansion with a generative feature model for object retrieval [J].
Chum, Ondrej ;
Philbin, James ;
Sivic, Josef ;
Isard, Michael ;
Zisserman, Andrew .
2007 IEEE 11TH INTERNATIONAL CONFERENCE ON COMPUTER VISION, VOLS 1-6, 2007, :496-+
[10]   Query-Adaptive Small Object Search Using Object Proposals and Shape-Aware Descriptors [J].
Das Bhattacharjee, Sreyasee ;
Yuan, Junsong ;
Tan, Yap-Peng ;
Duan, Ling-Yu .
IEEE TRANSACTIONS ON MULTIMEDIA, 2016, 18 (04) :726-737