Towards Large-Scale Object Instance Search: A Multi-Block N-Ary Trie
- 14 January 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems for Video Technology
- Vol. 31 (1) , 372-386
Abstract
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 largescale object instance search.Keywords
Funding Information
- National Nature Science Foundation of China (U1636109, 61425025, U1611461)
This publication has 45 references indexed in Scilit:
- Query-Adaptive Small Object Search Using Object Proposals and Shape-Aware DescriptorsIEEE Transactions on Multimedia, 2016
- A Distance-Computation-Free Search Scheme for Binary Code DatabasesIEEE Transactions on Multimedia, 2016
- Weighted Component Hashing of Binary Aggregated Descriptors for Fast Visual SearchIEEE Transactions on Multimedia, 2015
- INSTREACM Transactions on Multimedia Computing, Communications, and Applications, 2015
- Fast Exact Search in Hamming Space With Multi-Index HashingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image RetrievalIEEE Transactions on Pattern Analysis and Machine Intelligence, 2012
- Thick boundaries in binary space and their influence on nearest-neighbor searchPattern Recognition Letters, 2012
- A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming SpaceIEEE Transactions on Pattern Analysis and Machine Intelligence, 2012
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- Semantic hashingInternational Journal of Approximate Reasoning, 2009