Temporal Locality in Web Request Streams: Sources, Characteristics, and Caching Implications


Show simple item record

dc.contributor.author Jin, Shudong en_US
dc.contributor.author Bestavros, Azer en_US
dc.date.accessioned 2011-10-20T05:08:26Z
dc.date.available 2011-10-20T05:08:26Z
dc.date.issued 1999-10-10 en_US
dc.identifier.uri http://hdl.handle.net/2144/1791
dc.description.abstract Temporal locality of reference in Web request streams emerges from two distinct phenomena: the popularity of Web objects and the {\em temporal correlation} of requests. Capturing these two elements of temporal locality is important because it enables cache replacement policies to adjust how they capitalize on temporal locality based on the relative prevalence of these phenomena. In this paper, we show that temporal locality metrics proposed in the literature are unable to delineate between these two sources of temporal locality. In particular, we show that the commonly-used distribution of reference interarrival times is predominantly determined by the power law governing the popularity of documents in a request stream. To capture (and more importantly quantify) both sources of temporal locality in a request stream, we propose a new and robust metric that enables accurate delineation between locality due to popularity and that due to temporal correlation. Using this metric, we characterize the locality of reference in a number of representative proxy cache traces. Our findings show that there are measurable differences between the degrees (and sources) of temporal locality across these traces, and that these differences are effectively captured using our proposed metric. We illustrate the significance of our findings by summarizing the performance of a novel Web cache replacement policy---called GreedyDual*---which exploits both long-term popularity and short-term temporal correlation in an adaptive fashion. Our trace-driven simulation experiments (which are detailed in an accompanying Technical Report) show the superior performance of GreedyDual* when compared to other Web cache replacement policies. en_US
dc.description.sponsorship National Science Foundation (CCR-9706685); NSF ANIR grant en_US
dc.language.iso en_US en_US
dc.publisher Boston University Computer Science Department en_US
dc.relation.ispartofseries BUCS Technical Reports;BUCS-TR-1999-014 en_US
dc.subject Temporal locality of reference en_US
dc.subject Temporal correlation en_US
dc.subject Web access characterization and modeling en_US
dc.subject Zipf law en_US
dc.subject Cache replacement policies en_US
dc.subject Performance evaluation en_US
dc.title Temporal Locality in Web Request Streams: Sources, Characteristics, and Caching Implications en_US
dc.type Technical Report en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search OpenBU

Advanced Search


Deposit Materials