| Query Merging: Improving Query Subscription Processing in a Multicast Environment (2003) | |||||||||||||||||
Abstract | |||||||||||||||||
| This paper introduces techniques for reducing data dissemination costs of query subscriptions in amulticast 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 di erent heuristics and show that the performance of our heuristics is close to optimal. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||