| 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 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. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||