A NOVEL INDEX STRUCTURE FOR LARGE SCALE IMAGE DESCRIPTOR SEARCH

This paper presents a k-means based algorithm for approximate nearest neighbor search. The proposed Embedded k-Means algo-rithm is a two-level clustered index structure which consists of two groups of centroids; additionally, an inverted file is used for record-ing of the assignments. The coarse-to-fine structure achieves high search efficiency using multi-assignment operations on the coarse level. At the query stage, pruning strategies are utilized to balance the trade-off between search qualities and speeds. Our algorithm is able to explore the neighborhood space of a given query effi-ciently. Due to its good recall/selectivity and memory efficiency, the proposed algorithm is scalable and is able to process very large databases. Experimental results on SIFT and GIST image descrip-tor datasets show search performance better and comparable to the state-of-the-art approaches with lower memory usage and complex-ity. Index Terms — k-means, approximate nearest neighbor search, multi-assignment, pruning strategies, image descriptor indexing 1