Selective K-means Tree Search

Citations Over Time

Abstract

In object recognition and image retrieval, an inverted indexing method is used to solve the approximate nearest neighbor search problem. In these tasks, inverted indexing provides a nonexhaustive solution to large-scale search. However, a problem of previous inverted indexing methods is that a large-scale inverted index is required to achieve a high search recall rate. In this study, we address the problem of reducing the time required to build an inverted index without degrading the search accuracy and speed. Thus, we propose a selective k-means tree search method that combines the power of both hierarchical k-means tree and selective nonexhaustive search. Experiments based on approximate nearest neighbor search using a large dataset comprising one billion SIFT features showed that the hierarchical inverted file based on the selective k-means tree method could be built six times faster, while obtaining almost the same recall and search speed as the state-of-the-art inverted indexing methods.

Related Papers

• → The inverted multi-index(2012)206 cited
• → Vector and line quantization for billion-scale similarity search on GPUs(2019)12 cited
• → MiPai: Using the PP-Index to Build an Efficient and Scalable Similarity Search System(2009)30 cited
• Generic Inverted Index on the GPU(2016)
• → Searching for nearest neighbors with a dense space partitioning(2015)