Using Fagin's algorithm for merging ranked results in multimedia middleware
- 1 January 1999
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A distributed multimedia information system allows users to access data of different modalities, from different data sources, ranked by various combinations of criteria. Fagin (1996) 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.Keywords
This publication has 9 references indexed in Scilit:
- Scaling heterogeneous databases and the design of DiscoPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Object exchange across heterogeneous information sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Towards heterogeneous multimedia information systems: the Garlic approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Combining Fuzzy Information from Multiple SystemsJournal of Computer and System Sciences, 1999
- On saying “Enough already!” in SQLPublished by Association for Computing Machinery (ACM) ,1997
- Query caching and optimization in distributed mediator systemsACM SIGMOD Record, 1996
- Optimizing queries over multimedia repositoriesACM SIGMOD Record, 1996
- QBIC project: querying images by content, using color, texture, and shapePublished by SPIE-Intl Soc Optical Eng ,1993
- Extensible query processing in starburstPublished by Association for Computing Machinery (ACM) ,1989