Query merging: improving query subscription processing in a multicast environment
Authors:
- 14 January 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 15 (1) , 174-191
Abstract
This paper introduces techniques for reducing data dissemination costs of query subscriptions in a multicast environment. The reduction is achieved by merging queries with overlapping, but not necessarily equal, answers. The paper formalizes the query-merging problem and introduces a general framework and cost model for evaluating merging. We prove that the problem is NP-hard and propose exhaustive algorithms and three heuristic algorithms: the pair merging algorithm, the directed search algorithm, and the clustering algorithm. We develop a simulator, which uses geographical queries as a representative example for evaluating the different heuristics and show that the performance of our heuristics is close to optimal.Keywords
This publication has 25 references indexed in Scilit:
- Network interface to tactical communications2002
- Transactional publish/subscribeACM SIGMOD Record, 1998
- The PointCast network (abstract)ACM SIGMOD Record, 1998
- A framework for scalable dissemination-based systems1997
- Hits and miss-es: a year watching the WebComputer Networks and ISDN Systems, 1997
- Battlefield awareness and data dissemination (BADD) for the warfighter1997
- Mobile wireless computing: challenges in data managementCommunications of the ACM, 1994
- The Datacycle architectureCommunications of the ACM, 1992
- Polychannel systems for mass digital communicationsCommunications of the ACM, 1990
- Statistical profile estimation in database systemsACM Computing Surveys, 1988