Communication-Efficient Query Answering with Quality Guarantees in Client-Server Applications

We study how to reduce costs in client-server applications with dynamic data on the server. Client-side caching can help mitigate costs because the client can use the cached data to answer queries. Further, allowing some tolerance towards data staleness in answering queries makes it possible to significantly reduce costs. For example, if the user can tolerate data that was received 2 hours ago, we can use the cached data to provide the answer with a lower cost. In this paper we develop algorithms under different cost models. In particular, for a generalized cost model, we provide a 2-approximation offline algorithm, a competitive online algorithm, and a family of heuristics. We validate our methods through extensive experiments. 1