Taylor series prediction: a cache replacement policy based on second-order trend analysis

Abstract

Caching is one of the most effective techniques for improving the performance of Internet systems. The heart of a caching system is its page replacement policy, which decides which page to replace in a cache by a new one. Different caching policies have dramatically different effects on the system performance. In this paper, we extend the well-known GDSF caching policies to include not only access trend information, but also the dynamics of the access trend itself to the trends on access trends. The new trend policy that we propose, called Taylor Series Prediction (TSP) policy, provides more accurate prediction on future accessing trends when the access patterns vary greatly. We back up our claims through a series of experiments using web access traces.