Efficient Query Subscription Processing in a Multicast Environment A. Crespo, O. Buyukkokten, and H. Garcia-Molina   View Paper (PDF)   Return to Internet, Performance, and Systems Management Abstract This paper introduces techniques for reducing data dissemination costs of query subscriptions. 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 cost model for it. 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 for evaluating the different heuristics and show that the performance of our heuristics is close to optimal. Keywords: Query Processing, Data Dissemination, Query Merging, Query Subscriptions, Multicast of Query Results DiSC'01 Copyright ©2002 ACM Inc.