An on-line page-structure approximation scheme for Web proxies

To render a Web page, a browser must first download an HTML document, parse it, and then issue a sequence of additional requests to fetch the embedded objects according to the content of the HTML document. Therefore, it should be straightforward for Web proxies to accurately predict future client requests by considering the characteristics of such regular behavior. However, the strong bindings between embedded objects and their containing documents are often ignored by modern Web proxies because there still exists no efficient solution for Web proxies to obtain the knowledge of page structures without performing the computation-intensive operations of HTML parsing. In this paper, we propose an effective and low-overhead scheme for Web proxies to approximate page structures and refine the approximation as new client requests arrive. The results of simulation show that the approximation converges quickly and reaches high accuracy after a relatively small number of incoming requests have been processed.