An index structure for fast range search in Hamming space
Faisal Z. Qureshi1
Ken Q. Pu2
Ernesto Reina1,2
Visual Computing Lab1
Database Research Group2
Faculty of Science
University of Ontario Institute of Technology
2000 Simcoe St. N., Oshawa ON L1G 0C5
University of Ontario Institute of Technology
2000 Simcoe St. N., Oshawa ON L1G 0C5
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.
Publication
For technical details please look at the following publications