Using Fagin's algorithm for merging ranked results in multimedia middleware

Abstract

A distributed multimedia information system allows users to access data of different modalities, from different data sources, ranked by various combinations of criteria. In [6], 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 an actual multimedia middleware system, including a novel, incremental version of the algorithm that supports dynamic exploration of data. We show that the algorithm would perform well as part of a single multimedia server, and can even be effective in the distributed environment (for a limited set of queries), but that the assumptions it makes about random access limit its applicability dramatically. Our experience provides a better understanding of an important algorithm, and exposes an open problem for distributed multimedia information systems.