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.

A Two-Tiered On-Line Server-Side Bandwidth Reservation Framework for the Real-Time Delivery of Multiple Video Streams

The advent of virtualization and cloud computing technologies necessitates the development of effective mechanisms for the estimation and reservation of resources needed by content providers to deliver large numbers of video-on-demand (VOD) streams through the cloud. Unfortunately, capacity planning for the QoS-constrained delivery of a large number of VOD streams is inherently difficult as VBR encoding schemes exhibit significant bandwidth variability. In this paper, we present a novel resource management scheme to make such allocation decisions using a mixture of per-stream reservations and an aggregate reservation, shared across all streams to accommodate peak demands. The shared reservation provides capacity slack that enables statistical multiplexing of peak rates, while assuring analytically bounded frame-drop probabilities, which can be adjusted by trading off buffer space (and consequently delay) and bandwidth. Our two-tiered bandwidth allocation scheme enables the delivery of any set of streams with less bandwidth (or equivalently with higher link utilization) than state-of-the-art deterministic smoothing approaches. The algorithm underlying our proposed frame-work uses three per-stream parameters and is linear in the number of servers, making it particularly well suited for use in an on-line setting. We present results from extensive trace-driven simulations, which confirm the efficiency of our scheme especially for small buffer sizes and delay bounds, and which underscore the significant realizable bandwidth savings, typically yielding losses that are an order of magnitude or more below our analytically derived bounds.

Non-Rigid Shape from Image Streams

We present a framework for estimating 3D relative structure (shape) and motion given objects undergoing nonrigid deformation as observed from a fixed camera, under perspective projection. Deforming surfaces are approximated as piece-wise planar, and piece-wise rigid. Robust registration methods allow tracking of corresponding image patches from view to view and recovery of 3D shape despite occlusions, discontinuities, and varying illumination conditions. Many relatively small planar/rigid image patch trackers are scattered throughout the image; resulting estimates of structure and motion at each patch are combined over local neighborhoods via an oriented particle systems formulation. Preliminary experiments have been conducted on real image sequences of deforming objects and on synthetic sequences where ground truth is known.

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.

Robust Sketching and Aggregation of Distributed Data Streams

The data streaming model provides an attractive framework for one-pass summarization of massive data sets at a single observation point. However, in an environment where multiple data streams arrive at a set of distributed observation points, sketches must be computed remotely and then must be aggregated through a hierarchy before queries may be conducted. As a result, many sketch-based methods for the single stream case do not apply directly, as either the error introduced becomes large, or because the methods assume that the streams are non-overlapping. These limitations hinder the application of these techniques to practical problems in network traffic monitoring and aggregation in sensor networks. To address this, we develop a general framework for evaluating and enabling robust computation of duplicate-sensitive aggregate functions (e.g., SUM and QUANTILE), over data produced by distributed sources. We instantiate our approach by augmenting the Count-Min and Quantile-Digest sketches to apply in this distributed setting, and analyze their performance. We conclude with experimental evaluation to validate our analysis.

An Invariant Representation for Matching Trajectories across Uncalibrated Video Streams

We introduce a view-point invariant representation of moving object trajectories that can be used in video database applications. It is assumed that trajectories lie on a surface that can be locally approximated with a plane. Raw trajectory data is first locally approximated with a cubic spline via least squares fitting. For each sampled point of the obtained curve, a projective invariant feature is computed using a small number of points in its neighborhood. The resulting sequence of invariant features computed along the entire trajectory forms the view invariant descriptor of the trajectory itself. Time parametrization has been exploited to compute cross ratios without ambiguity due to point ordering. Similarity between descriptors of different trajectories is measured with a distance that takes into account the statistical properties of the cross ratio, and its symmetry with respect to the point at infinity. In experiments, an overall correct classification rate of about 95% has been obtained on a dataset of 58 trajectories of players in soccer video, and an overall correct classification rate of about 80% has been obtained on matching partial segments of trajectories collected from two overlapping views of outdoor scenes with moving people and cars.

Experimental evaluation of evolution and coevolution as agents of ecosystem change in Trinidadian streams.

Evolution has been shown to be a critical determinant of ecological processes in some systems, but its importance relative to traditional ecological effects is not well known. In addition, almost nothing is known about the role of coevolution in shaping ecosystem function. Here, we experimentally evaluated the relative effects of species invasion (a traditional ecological effect), evolution and coevolution on ecosystem processes in Trinidadian streams. We manipulated the presence and population-of-origin of two common fish species, the guppy (Poecilia reticulata) and the killifish (Rivulus hartii). We measured epilithic algal biomass and accrual, aquatic invertebrate biomass, and detrital decomposition. Our results show that, for some ecosystem responses, the effects of evolution and coevolution were larger than the effects of species invasion. Guppy evolution in response to alternative predation regimes significantly influenced algal biomass and accrual rates. Guppies from a high-predation site caused an increase in algae relative to guppies from a low-predation site; algae effects were probably shaped by observed divergence in rates of nutrient excretion and algae consumption. Rivulus-guppy coevolution significantly influenced the biomass of aquatic invertebrates. Locally coevolved populations reduced invertebrate biomass relative to non-coevolved populations. These results challenge the general assumption that intraspecific diversity is a less critical determinant of ecosystem function than is interspecific diversity. Given existing evidence for contemporary evolution in these fish species, our findings suggest considerable potential for eco-evolutionary feedbacks to operate as populations adapt to natural or anthropogenic perturbations.

A comparison between ultraviolet disinfection and copper alginate beads within a vortex bioreactor for the deactivation of bacteria in simulated waste streams with high levels of colour, humic acid and suspended solids

We show in this study that the combination of a swirl flow reactor and an antimicrobial agent (in this case copper alginate beads) is a promising technique for the remediation of contaminated water in waste streams recalcitrant to UV-C treatment. This is demonstrated by comparing the viability of both common and UV-C resistant organisms in operating conditions where UV-C proves ineffective - notably high levels of solids and compounds which deflect UV-C. The swirl flow reactor is easy to construct from commonly available plumbing parts and may prove a versatile and powerful tool in waste water treatment in developing countries.

Preparation and evaluation of Fuller's Earth Beads for removal of Cesium from waste streams

This work deals with removal of Cesium (radioactive waste) in dilute aqueous phase by adsorption. Fullers earth was used as an adsorbent. The adsorption capacity of Fullers earth with respect to Cesium was found to be high, 26.3 mg / g of adsorbent.

A programmable architecture for layered multimedia streams in IPv6 networks

A new configurable architecture is presented that offers multiple levels of video playback by accommodating variable levels of network utilization and bandwidth. By utilizing scalable MPEG-4 encoding at the network edge and using specific video delivery protocols, media streaming components are merged to fully optimize video playback for IPv6 networks, thus improving QoS. This is achieved by introducing “programmable network functionality” (PNF) which splits layered video transmission and distributes it evenly over available bandwidth, reducing packet loss and delay caused by out-of-profile DiffServ classes. An FPGA design is given which gives improved performance, e.g. link utilization, end-to-end delay, and that during congestion, improves on-time delivery of video frames by up to 80% when compared to current “static” DiffServ.

Selective hydrogenation of acetylene in ethylene rich feed streams at high pressure over ligand modified Pd/TiO2

The selective hydrogenation of acetylene from ethylene rich streams was conducted at high pressure and in the presence of CO over two 1 wt% loaded Pd/TiO2 catalysts with differing dispersions. Although, the more poorly dispersed sample did not result in high acetylene conversion only a small proportion of the total available ethylene was hydrogenated to ethane. The more highly dispersed sample was able to remove acetylene to a level below the detection limit but this was at the expense of significant proportion (ca. 30%) of the available ethylene. Modification of the catalysts by exposure to triphenyl phosphine or diphenyl sulfide and subsequent reduction at 393 K led to improved performance with increased conversion of acetylene and decreased propensity to hydrogenate ethylene resulting in an overall net gain in ethylene. The higher dispersed sample which had been ligand modified provided the best results overall and in particular for the diphenyl sulfide treated sample which was able to completely eliminate acetylene and still obtain a net gain in ethylene. The differences observed are thought to be due to the creation of appropriate active ensembles of Pd atoms which are able to accommodate acetylene but have limited ability to adsorb ethylene. Sub-surface hydrogen formation was suppressed, but not eliminated, by exposure to modifier.