Minimal web patch generation for incremental web caching

Abstract

The principle of web caching is to keep frequently requested items close to where they are needed. The cache may reside in local computers, dedicated cache proxies, or clients that share their local caches. Frequent updates on the original web server shorten the useful lifetime of cache contents. If the update is minor, the stale cache still contains valuable information. An incremental update and delivery scheme, which allows the client to fetch a patch from the original web server to update the stale cache, can improve the caching performance. The paper focuses on the minimal patch generation problem. Web objects are transformed into ordered labelled trees, and the patch is generated in tree space. The paper models the web patch problem as a minimal set cover problem with dynamic weights. This problem can be solved using available solutions of the fixed weighted minimal set cover problem by imposing appropriate conditions. © IEE, 2005.