Efficient processing of complex similarity queries - queries consisting of more than one similarity predicate - has some peculiarities with respect to traditional (Boolean) query processing. For instance, since the "similarity score" (grade) an object gets for the whole query depends on the scores it gets for the single predicates, and on how such scores are combined, the evaluation of similarity predicates cannot be performed independently. As an example, consider an image database where a user can retrieve objects by means of both shape and color features, and assume that the two sets of feature values are separately indexed.
In order to retrieve the best match for the query
(shape='circular') and (color='red')it is not correct to retrieve only the best match for color (using an index on color) and the best match for shape (using an index on shape), since the best match for the overall query needs not to be the best match for the single conjuncts.
The state-of-the-art solution to the above kind of queries is the algorithm A0 presented by Fagin in a recent work, which returns the k best matches (nearest neighbors) for a complex query, on the assumption that evaluation of the single predicates in the query is carried out by independent subsystems, and that access to one subsystem is "synchronized" with that to others.
We concentrate on a relevant class of complex similarity queries, which arises when all the similarity predicates refer to a single feature. As an example, consider an image database whose objects can be retrieved using a Query-by-Sketch modality, e.g. where a user draws, by means of a graphic editor, a simple shape. The system, then, searches the DB, and returns to the user those, say, 10 images which contain a shape best matching (according to given similarity criterion for shapes) the user's input. Now, the user can "refine" the search by pointing out to the system objects which are similar to what he/she had in mind and which are actually not. Suppose the user specifies two "positive" and one "negative" samples and asks for another search. The system, thus, has to search the DB for such 10 objects which are most similar to both positive samples, and, at the same time, not similar to the negative sample. This interactive process can be iterated several times, until the user gets satisfied with system's output.
An interactive retrieval process, such as the one sketched above, typically occurs when querying multimedia repositories, where the user has no clear idea on how to express what he/she is looking for, and relies on previous results to improve the effectiveness of subsequent requests.
The strategy we proposed in EDBT 98 starts from the idea to extend access methods in such a way that they can process complex queries as a whole, thus evaluating multiple predicates at a time. Since access methods typically evaluate the similarity of two objects by means of their distance in some feature space, we need to ground our proposed extension on a sound formal basis, which has to specify how multiple distance measures (corresponding to multiple similarity predicates) should be combined to perform a both efficient and correct pruning of the search space.
We extended the M-tree access method by specializing the MTpred class with complex predicates. In the provided library we included the definition of classes implementing complex predicates for the fuzzy language (where simple predicates are combined by using logical connectives like and, or, and not).
If the user wants to write new extensions for other complex predicates, he/she has to derive a class from the MTpred base class and to provide the Consistent method, returning FALSE only if the considered entry does not satisfy the complex predicate.