A Multi-Block N-Ary Trie Structure for Exact R-Neighbour Search in Hamming Space

A Multi-Block N-Ary Trie Structure for Exact R-Neighbour Search in Hamming Space
Title:
A Multi-Block N-Ary Trie Structure for Exact R-Neighbour Search in Hamming Space
Other Titles:
2017 IEEE International Conference on Image Processing
DOI:
Publication Date:
17 September 2017
Citation:
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 find the near neighbours by checking all buckets of a Hamming ball centered at the query. However, the problem is that these methods spend most of the time visiting NULL buckets (lookup misses). In this paper, we adopt trie structures to index binary codes. We consider several continuous bits of a bina- ry string as a block and use it as an atomic indexing element in trie structures, which is efficient in both access speed and memory us- age. Further, our method searches the near neighbours of a query by utilizing the records of nodes in trie structures to avoid lookup miss- es. We name the proposed indexing structure as Multi-Block Bitwise Trie (MBBT). A theoretical analysis is given to indicate that MBBT has less time cost than other hash-based methods. Moreover, exten- sive results show that MBBT outperforms state-of-the-art algorithms over several large scale benchmarks.
License type:
PublisherCopyrights
Funding Info:
Description:
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
ISBN:

Files uploaded:

File Size Format Action
icip-mbbt.pdf 3.61 MB PDF Open