PackCache: An Online Cost-Driven Data Caching Algorithm in the Cloud

In this paper, we study a data caching problem in the cloud environment, where multiple frequently co-utilised data items could be packed as a single item being transferred to serve a sequence of data requests dynamically with reduced cost. To this end, we propose an online algorithm with respect to a homogeneous cost model, called PackCache, that can leverage the FP-Tree technique to mine those frequently co-utilised data items for packing whereby the incoming requests could be cost-effectively served online by exploiting the concept of anticipatory caching. We show the algorithm is 2/alpha competitive, reaching the lower bound of the competitive ratio for any deterministic online algorithm on the studied caching problem, and also time and space efficient to serve the requests. Finally, we evaluate the performance of the algorithm via experimental studies to show its actual cost-effectiveness and scalability.

Automated summary

This paper addresses a data caching problem in the cloud environment and proposes an online algorithm called PackCache, which leverages the FP-Tree technique to mine frequently co-utilised data items for cost-effective serving of incoming requests. The algorithm is shown to be 2/alpha competitive, reaching the lower bound of the competitive ratio, and also efficient in terms of time and space.