Stanford InfoLab Publication Server

Approximate Caching for Continuous Queries over Distributed Data Sources

Olston, Chris and Widom, Jennifer (2002) Approximate Caching for Continuous Queries over Distributed Data Sources. Technical Report. Stanford.

WarningThere is a more recent version of this item available.



Monitoring continuous queries over distributed data sources typically requires replicating data continuously at a central location for query monitoring, incurring significant communication overhead when source data is updated. We propose a new technique that reduces communication overhead by using <i>approximate caching. Our approach enables users to register continuous queries with precision constraints. The system caches approximate data values with just enough accuracy to meet the precision constraints of all registered continuous queries at all times, while dynamically and adaptively allocating imprecision among cached values using an algorithm that minimizes data refreshes. Through experimental simulation over synthetic and real-world data, we demonstrate the effectiveness of our approach in reducing communication costs significantly compared with other approaches. Most importantly, we show that our algorithm enables users to trade precision for communication cost at a fine granularity by individually adjusting the precision constraints of continuous queries in a large multi-query workload, a feature that no known previous algorithm can provide.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:approximate caching, TRAPP
Subjects:Computer Science > Distributed Systems
Related URLs:Project Homepage
ID Code:574
Deposited By:Import Account
Deposited On:17 Feb 2002 16:00
Last Modified:25 Dec 2008 10:01

Available Versions of this Item

Download statistics

Repository Staff Only: item control page