Olston, Chris and Widom, Jennifer (2002) Approximate Caching for Continuous Queries over Distributed Data Sources. Technical Report. Stanford.
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||http://infolab.stanford.edu/trapp/|
|Deposited By:||Import Account|
|Deposited On:||17 Feb 2002 16:00|
|Last Modified:||25 Dec 2008 10:01|
Available Versions of this Item
- Approximate Caching for Continuous Queries over Distributed Data Sources. (deposited 17 Feb 2002 16:00) [Currently Displayed]
Repository Staff Only: item control page