This paper proposes a hybrid query refinement model for distance-based index structures supporting content-based image retrievals. The framework refines a query by considering both the low-level feature space as well as the high-level semantic interpretations separately. Thus, it successfully handles queries where the gap between the feature components and the semantics is large. It refines the low-level feature space, indexed by the distance based index structure, in multiple iterations by introducing the concept of multipoint query in a metric space. It refines the high-level semantic space by dynamically adjusting the constructs of a framework, called the Markov Model Mediator (MMM), utilized to introduce the semantic relationships in the index structure. A k-nearest neighbor (k-NN) algorithm is designed to handle similarity searches that refine a query in multiple iterations utilizing the proposed hybrid query refinement model. Extensive experiments are performed demonstrating an increased relevance of query results in subsequent iterations while incurring a low computational overhead. Further, an evaluation metric, called the Model_Score, is proposed to compare the performance of different retrieval frameworks in terms of both computation overhead and query result relevance. This metric enables the users to choose the retrieval framework appropriate for their requirements.
Top1. Introduction
An index structure is one of the major components of a database management system as it assists in efficiently organizing the data and enables quick and accurate retrieval. There are multidimensional index structures such as Berchtold and Keim (1996), Chatterjee and Chen (2006), Ciaccia, Patella, and Zezula (1997), and Guttman (1984), which can accommodate the atypical multidimensional representation of multimedia data. But enabling them to efficiently support the popular retrieval strategies, such as content-based image and video retrievals, is still a challenge due to the semantic information carried by them. The semantic interpretation of a multimedia data is subjective and varies from user to user or even from iteration to iteration for an individual user. This makes the similarity queries issued for multimedia data imprecise in nature. A single iteration or a fixed query representation is not enough to capture the user requirements during the retrieval process. Thus, attempts to capture the users' interest pattern are made with a strategy called query refinement having two major components namely query modification and query re-weighting (Porkaew, Chakrabarti, & Mehrotra, 1999). In query modification, the query representation is modified in each iteration to reach the region in the feature space which best describes the feature components of the users' requirement. In query re-weighting, the semantic component of a query is modified in subsequent iterations to better capture the users' perception. As a query is refined, the similarity search and the distance functions utilized to determine the similarity need to be modified as well. Automatically, it becomes necessary that the index structures, supporting the similarity searches, also accommodate the modified distance functions developed for the refined queries.
Multidimensional index structures can be broadly divided into two categories viz. feature-based and distance-based. A feature based indexing technique projects an image as a feature vector into a multidimensional space and index it. Some feature based index structures are KDB-tree (Robinson, 1981), R-tree (Guttman, 1984), etc. On the other hand distance based indexing structures are built based on the distances or similarities between two data objects. Some famous distance based index structures are M-Tree (Ciaccia, Patella, & Zezula, 1997) and vp-tree (Yianilos, 1993). Both categories are useful depending on the dataset in hand and the application that need to be supported. Though query refinement strategies have been designed for feature-based index structures as in Porkaew, Ortega, and Mehrotra (1999), Chakrabarti and Mehrotra (1999), and Chakrabarti, Porkaew, Ortega, and Mehrotra (2004) but to the best of our knowledge there has been no such attempt for distance-based index structures. Another major drawback is that if the semantic information of a multimedia object cannot be interpreted completely in terms of the inter and intra feature weights (when the semantic gap is large), refinement strategies (Porkaew, Chakrabarti, & Mehrotra, 1999) fail to produce satisfactory results. The semantic gap is a very common problem for multimedia data and is illustrated in Figure 1 for an image database where the feature-level similarity failed to capture users' high-level semantic perception. Figure 1(a) represents the inverse of the Euclidean Distance (similarity) between the feature vectors of an image with other images of a database. Figure 1(b) represents the high-level semantic relationship between the same image with other images in the database. It’s seen that the image, with which the image under consideration shares a low similarity in terms of feature space, has a very high semantic relationship with it.
Figure 1. Graphs depicting that feature-level similarity fail to capture users' high-level perception