Stanford InfoLab Publication Server

Efficient Query Subscription Processing in a Multicast Environment

Crespo, Arturo and Buyukkokten, Orkut and Garcia-Molina, Hector (2000) Efficient Query Subscription Processing in a Multicast Environment. Technical Report. Stanford InfoLab. (Publication Note: 16th International Conference on Data Engineering (ICDE 2000) February 29 - March 3, 2000, San Diego, CA.)




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.

Item Type:Techreport (Technical Report)
Additional Information:Previous number = SIDL-WP-2000-0142
Subjects:Computer Science > Digital Libraries
Projects:Digital Libraries
Related URLs:Project Homepage
ID Code:477
Deposited By:Import Account
Deposited On:30 Oct 2001 16:00
Last Modified:27 Dec 2008 12:08

Download statistics

Repository Staff Only: item control page