Characterizing Reference Locality in the WWW

As 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.

On the Intrinsic Locality Properties of Web Reference Streams

There has been considerable work done in the study of Web reference streams: sequences of requests for Web objects. In particular, many studies have looked at the locality properties of such streams, because of the impact of locality on the design and performance of caching and prefetching systems. However, a general framework for understanding why reference streams exhibit given locality properties has not yet emerged. In this work we take a first step in this direction, based on viewing the Web as a set of reference streams that are transformed by Web components (clients, servers, and intermediaries). We propose a graph-based framework for describing this collection of streams and components. We identify three basic stream transformations that occur at nodes of the graph: aggregation, disaggregation and filtering, and we show how these transformations can be used to abstract the effects of different Web components on their associated reference streams. This view allows a structured approach to the analysis of why reference streams show given properties at different points in the Web. Applying this approach to the study of locality requires good metrics for locality. These metrics must meet three criteria: 1) they must accurately capture temporal locality; 2) they must be independent of trace artifacts such as trace length; and 3) they must not involve manual procedures or model-based assumptions. We describe two metrics meeting these criteria that each capture a different kind of temporal locality in reference streams. The popularity component of temporal locality is captured by entropy, while the correlation component is captured by interreference coefficient of variation. We argue that these metrics are more natural and more useful than previously proposed metrics for temporal locality. We use this framework to analyze a diverse set of Web reference traces. We find that this framework can shed light on how and why locality properties vary across different locations in the Web topology. For example, we find that filtering and aggregation have opposing effects on the popularity component of the temporal locality, which helps to explain why multilevel caching can be effective in the Web. Furthermore, we find that all transformations tend to diminish the correlation component of temporal locality, which has implications for the utility of different cache replacement policies at different points in the Web.

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

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.

GreedyDual* Web Caching Algorithm: Exploiting the Two Sources of Temporal Locality in Web Request Streams

The relative importance of long-term popularity and short-term temporal correlation of references for Web cache replacement policies has not been studied thoroughly. This is partially due to the lack of accurate characterization of temporal locality that enables the identification of the relative strengths of these two sources of temporal locality in a reference stream. In [21], we have proposed such a metric and have shown that Web reference streams differ significantly in the prevalence of these two sources of temporal locality. These finding underscore the importance of a Web caching strategy that can adapt in a dynamic fashion to the prevalence of these two sources of temporal locality. In this paper, we propose a novel cache replacement algorithm, GreedyDual*, which is a generalization of GreedyDual-Size. GreedyDual* uses the metrics proposed in [21] to adjust the relative worth of long-term popularity versus short-term temporal correlation of references. Our trace-driven simulation experiments show the superior performance of GreedyDual* when compared to other Web cache replacement policies proposed in the literature.

Paleoenvironmental reconstruction of the coastal Monte Léon and Santa Cruz formations (Early Miocene) at Rincón del Buque, Southern Patagonia: A revisited locality

© 2015 Elsevier Ltd.Sedimentological, ichnological and paleontological analyses of the Early Miocene uppermost Monte León Formation and the lower part of the Santa Cruz Formation were carried out in Rincón del Buque (RDB), a fossiliferous locality north of Río Coyle in Santa Cruz Province, Patagonia, Argentina. This locality is of special importance because it contains the basal contact between the Monte Léon (MLF) and the Santa Cruz (SCF) formations and because it preserves a rich fossil assemblage of marine invertebrates and marine trace fossils, and terrestrial vertebrates and plants, which has not been extensively studied. A ~90m-thick section of the MLF and the SCF that crops out at RDB was selected for this study. Eleven facies associations (FA) are described, which are, from base to top: subtidal-intertidal deposits with Crassotrea orbignyi and bioturbation of the Skolithos-Cruziana ichnofacies (FA1); tidal creek deposits with terrestrial fossil mammals and Ophiomorpha isp. burrows (FA2); tidal flat deposits with Glossifungites ichnofacies (FA3); deposits of tidal channels (FA4) and tidal sand flats (FA5) both with and impoverish Skolithos ichnofacies associated; marsh deposits (FA6); tidal point bar deposits recording a depauperate mixture of both the Skolithos and Cruziana ichnofacies (FA7); fluvial channel deposits (FA8); fluvial point bar deposits (FA9); floodplain deposits (FA10); and pyroclastic and volcaniclastic deposits of the floodplain where terrestrial fossil mammal remains occur (FA11).The transition of the MLF-SCF at RDB reflects a changing depositional environment from the outer part of an estuary (FA1) through the central (FA2-6) to inner part of a tide-dominated estuary (FA7). Finally a fluvial system occurs with single channels of relatively low energy and low sinuosity enclosed by a broad, low-energy floodplain dominated by partially edaphized ash-fall, sheet-flood, and overbank deposits (FA8-11). Pyroclastic and volcaniclastic materials throughout the succession must have been deposited as ash-fall distal facies in a fluvial setting and also were carried by fluvial streams and redeposited in both estuarine and fluvial settings. These materials preserve most of the analyzed terrestrial fossil mammals that characterize the Santacrucian age of the RDB's succession. Episodic sedimentation under volcanic influence, high sedimentation rates and a relatively warm and seasonal climate are inferred for the MLF and SCF section.Lateral continuity of the marker horizons at RDB serve for correlation with other coastal localities such as the lower part of the coastal SCF south of Río Coyle (~17.6-17.4Ma) belonging to the Estancia La Costa Member of the SCF.

Constructions of locality and gender and their impact on the educational aspirations of working class children

Over recent years the moral panic that has surrounded 'boys' underachievement' has tended to encourage crude and essentialist comparisons between all boys and all girls and to eclipse the continuing and more profound effects on educational achievement exerted by social class and 'race'/ethnicity. While there are differences in educational achievement between working class boys and girls, these differences are relatively minor when comparing the overall achievement levels of working class children with those from higher, professional social class backgrounds. This paper argues that a need exists therefore for researchers to fully contextualise the gender differences that exist in educational achievement within the over-riding contexts provided by social class and 'race'/ethnicity. The paper provides an example of how this can be done through a case study of 11-year-old children from a Catholic, working class area in Belfast. The paper shows how the children's general educational aspirations are significantly mediated by their experiences of the local area in which they live. However, the way in which the children come to experience and construct a sense of locality differs between the boys and girls and this, it is argued, helps to explain the more positive educational aspirations held by some of the girls compared to the boys. The paper concludes by considering the relevance of locality for understanding its effects on educational aspirations among other working class and/or minority ethnic communities.

Low power field programmable gate array implementation of fast digital signal processing algorithms: characterisation and manipulation of data locality

Dynamic power consumption is very dependent on interconnect, so clever mapping of digital signal processing algorithms to parallelised realisations with data locality is vital. This is a particular problem for fast algorithm implementations where typically, designers will have sacrificed circuit structure for efficiency in software implementation. This study outlines an approach for reducing the dynamic power consumption of a class of fast algorithms by minimising the index space separation; this allows the generation of field programmable gate array (FPGA) implementations with reduced power consumption. It is shown how a 50% reduction in relative index space separation results in a measured power gain of 36 and 37% over a Cooley-Tukey Fast Fourier Transform (FFT)-based solution for both actual power measurements for a Xilinx Virtex-II FPGA implementation and circuit measurements for a Xilinx Virtex-5 implementation. The authors show the generality of the approach by applying it to a number of other fast algorithms namely the discrete cosine, the discrete Hartley and the Walsh-Hadamard transforms.

Non-locality of two ultracold trapped atoms

We undertake a detailed analysis of the non-local properties of the fundamental problem of two trapped, distinguishable neutral atoms that interact with a short-range potential characterized by an s-wave scattering length. We show that this interaction generates continuous variable (CV) entanglement between the external degrees of freedom of the atoms and consider its behaviour as a function of both, the distance between the traps and the magnitude of the inter-particle scattering length. We first quantify the entanglement in the ground state of the system at zero temperature and then, adopting a phase-space approach, test the violation of the Clauser-Horn-Shimony-Holt inequality at zero and non-zero temperature and under the effects of general dissipative local environments.