Paper Info
Title
A Multi-Block N-Ary Trie Structure For Exact R-Neighbour Search In Hamming Space
Abstract
This paper proposes a novel algorithm to solve the exact r-neighbour search problem in Hamming space. Existing r-neighbour search methods typically adopt hash table to index binary codes. Given a query, existing approaches search the nearest neighbours by checking all buckets of a Hamming ball centered at the query. The problem is these methods spend most of search time visiting empty buckets (lookup misses). In this paper, we adopt trie structure to index binary codes. We consider several continuous bits of a binary string as a block and use it as an atomic indexing element in trie structure, which is efficient in access speed and memory usage. Our method searches the nearest neighbours of a query by utilizing the records of nodes in trie structure to avoid lookup misses. We name the proposed indexing structure as Multi-Block N-ary Trie (MBNT). A theoretical analysis is given to prove that MBNT has less time cost than other hash-based methods. Extensive results show that MBNT outperforms state-of-the-art algorithms on several large scale benchmarks.
Year
Venue
Keywords
2017
2017 24TH IEEE INTERNATIONAL CONFERENCE ON IMAGE PROCESSING (ICIP)
Binary Code, Trie, Index, R-Neighbour
Field
DocType
ISSN
Hamming code,Pattern recognition,Computer science,Binary code,Search engine indexing,Theoretical computer science,Hamming distance,Hash function,Artificial intelligence,Hamming space,Trie,Hash table
Conference
1522-4880
Citations 
PageRank 
References 
0
0.34
0
Authors
6
Name
Order
Citations
PageRank
Yicheng Huang152.08
Ling-yu Duan21770124.87
Zhe Wang3122.50
Jie Lin43495502.80
Vijay Chandrasekhar519122.83
Tiejun Huang649.05