My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Project Information
Members

Abstract. We consider a new online problem, called caching for queries and updates, which encompasses three expansions to standard caching: Requests can be for multiple data objects (or “file bundles”), requests can be queries that return results much smaller than the data they access, or there may be updates to the data at the source. Different combinations of these expansions arise in modern applications such as scientific computing on data-grids and middle-tier caching in web-based databases. We present a randomized online (2alpha + 2)-competitive algorithm for this problem, given any alpha-competitive algorithm for the well studied object caching (multi-size paging) problem. This is the first known online algorithm for the combined problem and for several simpler combinations of the three extensions. This algorithm is both space-efficient and computationally tractable and has bounded overhead for control communication. - Little, P. and Chaudhary, A. 2008. Object Caching for Queries and Updates. To appear in Proceedings of the 3rd annual Workshop on Algorithms and Computation (WALCOM 2009).

Powered by Google Project Hosting