An index structure for fast range search in Hamming space

Faisal Z. Qureshi (http://faculty.uoit.ca/qureshi)
Ken Q. Pu (http://db.science.uoit.ca/)
Ernesto Reina

Abstract

This paper addresses the problem of indexing and querying very large databases of binary vectors. Such databases of binary vectors are a common occurrence in domains such as information retrieval and computer vision. We propose an indexing structure consisting of a compressed bitwise trie and a hash table for supporting range queries in Hamming space. The index structure, which can be updated incrementally, is able to solve the range queries for any radius. Our approach significantly outperforms state-of-the-art approaches.

Trie Indexing
Trie Indexing

Publication

For technical details please look at the following publications