Approximate Caching for Continuous Queries over Distributed Data Sources

Abstract

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.

Available Versions of this Item

• Approximate Caching for Continuous Queries over Distributed Data Sources. (deposited 17 Feb 2002 16:00) [Currently Displayed]
  • Adaptive Filters for Continuous Queries over Distributed Data Streams. (deposited 14 Nov 2002 16:00)
    • Adaptive Filters for Continuous Queries over Distributed Data Streams. (deposited 12 Feb 2003 16:00)