Fast image retrieval: Query pruning and early termination

Publication Type:
Journal Article
IEEE Transactions on Multimedia, 2015, 17 (5), pp. 648 - 659
Issue Date:
Filename Description Size
07054551.pdfPublished Version1.84 MB
Adobe PDF
Full metadata record
© 1999-2012 IEEE. Efficiency is of great importance for image retrieval systems. For this pragmatic issue, this paper proposes a fast image retrieval framework to speed up the online retrieval process. To this end, an impact score for local features is proposed in the first place, which considers multiple properties of a local feature, including TF-IDF, scale, saliency, and ambiguity. Then, to decrease memory consumption, the impact score is quantized to an integer, which leads to a novel inverted index organization, called Q-Index. Importantly, based on the impact score, two closely complementary strategies are introduced: query pruning and early termination. On one hand, query pruning discards less important features in the query. On the other hand, early termination visits indexed features only with high impact scores, resulting in the partial traversing of the inverted index. Our approach is tested on two benchmark datasets populated with an additional 1 million images to account as negative examples. Compared with full traversal of the inverted index, we show that our system is capable of visiting less than 10% of the 'should-visit' postings, thus achieving a significant speed-up in query time while providing competitive retrieval accuracy.
Please use this identifier to cite or link to this item: