cx-Sim: A Metric Access Method for Similarity Queries with Additional Conditions

Abstract

The fast growth of complex data repositories, such as images, videos and time series, in recent years is intensifying the importance of developing efficient search strategies over these data types. Applications that deal with complex data employ similarity queries to retrieve data, often combining similarity conditions with conditions over other associated attributes of traditional data types. There are several indexing structures for answering similarity queries, however most of them do not work when there are additional search conditions. The existing structures that answer queries combining conditions over complex and traditional attributes only support keyword-based conditions. This article presents a new metric access method to efficiently execute similarity queries with additional conditions over complex data. The proposed method, called the Condition-eXtended Similarity tree (cx-Sim tree), is a composite index that is able to answer similarity queries with general conditions (not only keyword-based), combining an ordered tree to store a traditional attribute with a forest of similarity trees to store a complex attribute. The article also presents results of experiments using three real datasets that show that our approach outperformed existing methods in a great extent.