Using Fagin's Algorithm For Merging Ranked Results In Multimedia Middleware

A multimedia middleware system allows applications to access a variety of data, of different modalities, stored in data sources with their own specialized search capabilities. In such a system, the user can request a set of objects be ranked by a particular property, or by a combination of properties. In [Fag96], Fagin gives an algorithm for efficiently merging multiple ordered streams of ranked results, to form a new stream ordered by a combination of those ranks. In this paper, we describe the implementation of Fagin's algorithm in the Garlic multimedia middleware system [C+95]. While the algorithm is quite simple, adapting it to the middleware environment poses a number of challenges, and raises questions about the applicability of the algorithm. We discuss the issues involved in implementing Fagin's algorithm in this environment and identify several assumptions on which the algorithms depends (but which do not necessarily hold). We then describe the results of experiments in which we compare the algorithm with other execution strategies for a range of queries such as might be posed by users of Garlic. Based on these results, we identify the conditions under which Fagin's algorithm is likely to be useful, and suggest some variations of the algorithm to make it more generally applicable.