A queries-based structure for similarity searching in static and dynamic metric spaces

Abstract

This paper aims to develop a metric indexing method that uses users’ queries for reducing the search cost of similarity search systems and for avoiding the insertion cost in dynamic data sets. We have proposed an indexing method which is able to improve its structure based on users’ queries. The proposed method, called I-Clusters, is a metric clustering based method, extended from the List of Clusters method. This method decreases the construction costs, and it improves the search cost after the execution of queries. The I-Clusters method allows solving the trade-off between the construction cost and the searching cost, and it also allows indexing dynamic datasets without additional cost of objects insertion. The experiment results show that the I-Clusters method significantly reduces the search cost based on queries execution, and the search performance of the proposed method can reach that of List of Clusters. Keywords: Content-based retrieval, Similarity search, Data structures, Indexing, Nearest neighbours, Range query