Show simple item record

dc.contributor.authorAlmeida, Virgílioen_US
dc.contributor.authorBestavros, Azeren_US
dc.contributor.authorCrovella, Marken_US
dc.contributor.authorde Oliveira, Adrianaen_US
dc.date.accessioned2011-10-20T04:32:23Z
dc.date.available2011-10-20T04:32:23Z
dc.date.issued1996-06-21
dc.identifier.citationAlmeida, Virgilio; Bestavros, Azer; Crovella, Mark; deOliveira, Adriana. "Characterizing Reference Locality in the WWW", Technical Report BUCS-1996-011, Computer Science Department, Boston University, June 21, 1996. [Available from: http://hdl.handle.net/2144/1587]
dc.identifier.urihttps://hdl.handle.net/2144/1587
dc.description.abstractAs the World Wide Web (Web) is increasingly adopted as the infrastructure for large-scale distributed information systems, issues of performance modeling become ever more critical. In particular, locality of reference is an important property in the performance modeling of distributed information systems. In the case of the Web, understanding the nature of reference locality will help improve the design of middleware, such as caching, prefetching, and document dissemination systems. For example, good measurements of reference locality would allow us to generate synthetic reference streams with accurate performance characteristics, would allow us to compare empirically measured streams to explain differences, and would allow us to predict expected performance for system design and capacity planning. In this paper we propose models for both temporal and spatial locality of reference in streams of requests arriving at Web servers. We show that simple models based only on document popularity (likelihood of reference) are insufficient for capturing either temporal or spatial locality. Instead, we rely on an equivalent, but numerical, representation of a reference stream: a stack distance trace. We show that temporal locality can be characterized by the marginal distribution of the stack distance trace, and we propose models for typical distributions and compare their cache performance to our traces. We also show that spatial locality in a reference stream can be characterized using the notion of self-similarity. Self-similarity describes long-range correlations in the dataset, which is a property that previous researchers have found hard to incorporate into synthetic reference strings. We show that stack distance strings appear to be strongly self-similar, and we provide measurements of the degree of self-similarity in our traces. Finally, we discuss methods for generating synthetic Web traces that exhibit the properties of temporal and spatial locality that we measured in our data.en_US
dc.description.sponsorshipNational Science Foundation (CCR-9308344, CCR-9501822); CNPq-Brazilen_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1996-011
dc.subjectSelf-similarityen_US
dc.subjectLong-range dependenceen_US
dc.subjectDistance stringsen_US
dc.subjectReference localityen_US
dc.subjectCachingen_US
dc.subjectPerformance modelingen_US
dc.titleCharacterizing Reference Locality in the WWWen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record