|
|
|
 |
|
 |
|
Using Fagin's Algorithm for Merging Ranked Results in Multimedia Middleware
|
E. Wimmers,
L. Haas,
M. Roth, and
C. Braendli
View Paper (PDF)
Return to Mediators and Query Processing
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.
Copyright(C) 2000 ACM
|
|
|
|
|
|
|
