Framework for efficient processing of content-based fuzzy Cartesian queries

Abstract

It has become increasingly important for multimedia databases to provide capabilities for content-based retrieval of multi-modal data at multiple abstraction levels for various decision support applications. These decision support applications commonly require the evaluation of fuzzy spatial or temporal Cartesian product of objects that have been retrieved based on their similarity to the target object in terms of color, shape, or texture features. In this paper, we propose an enhanced sequential query processing algorithm to process fuzzy Cartesian queries. This algorithm extend the Viterbi that has been well known in wireless communication area and Fagin's algorithm to evaluate combinations of candidate objects that satisfy the fuzzy Cartesian query. To retrieve the top K combinations from a fuzzy Cartesian product of M simple objects with each of which has L candidates, the computational complexity of the proposed algorithm is O(ML(log(L)+√LK+K2log(K))). This compares very favorably with respect to O(LM) required by the brute force evaluation or O(KML2(C+log(K))) required by the previously proposed SPROC algorithm to retrieve the Cartesian product of M simple objects.