A Heuristic Algorithm for Combining Fuzzy Results in Multimedia Databases

Ramakrishna, M.V., Nepal, S. and Srivastava, P.K.

This paper deals with the issue of combining fuzzy results obtained from two individual systems in multimedia query processing. Consider a query such as retrieve images similar to I1 by color AND with associated text flower. Suppose we have a color subsystem which can return a sorted list of images based on similarity with I1 and a text subsystem which can return a sorted list of images based on similarity with flower. Our task is to combine these two results. In other words, we need to evaluate the fuzzy combining function AND, giving a sorted list of the images. Fagin has proved that the probabilistic complexity of the problem is almost linear (Fagin 1995), and our multi-step algorithm (Nepal & M.V. Ramakrishna 1999) is an optimal uniform algorithm (Fagin, Lotem & Naor 2001). In view of this inherent limitation, we investigated a non-uniform heuristic approach. In this paper, we discuss the problems of processing such queries, also referred to as aggregation queries in multimedia databases. The experimental results presented show that our 'minimum depth first search' heuristic approach outperforms other uniform algorithms in general and by over 90% when the distribution of similarity values is not uniform.

Cite as: Ramakrishna, M.V., Nepal, S. and Srivastava, P.K. (2002). A Heuristic Algorithm for Combining Fuzzy Results in Multimedia Databases. In Proc. Thirteenth Australasian Database Conference (ADC2002), Melbourne, Australia. CRPIT, 5. Zhou, X., Ed. ACS. 141-145.

(from crpit.com) (local if available)