Raccoon

Many database applications that need to disseminate dynamic information from a server to various clients can suffer from heavy communication costs. Data caching at a client can help mitigate these costs, particularly when individual $\push$-$\pull$ decisions are made for the different semantic regions in the data space. The server is responsible for notifying the client about updates in the $\push$ regions. The client needs to contact the server for queries that ask for data in the $\pull$ regions. We call the idea of partitioning the data space into $\push$-$\pull$ regions to minimize communication cost {\em data gerrymandering}. In this paper we present solutions to technical challenges in adopting this simple but powerful idea. We give a provably optimal-cost dynamic programming algorithm for gerrymandering on a single query attribute. We propose a family of efficient heuristics for gerrymandering on multiple query attributes. We handle the dynamic case in which the workloads of queries and updates evolve over time. We validate our methods through extensive experiments on real and synthetic data sets.

PDF (pdf)