Distributed stream processing systems offer a highly scalable and dynamically configurable platform for time-critical applications ranging from real-time, exploratory data mining to high performance transaction processing. Resource management for distributed stream processing systems is complicated by a number of factors processing elements are constrained by their producer-consumer relationships, data and processing rates can be highly bursty, and traditional measures of effectiveness, such as utilization, can be misleading. In this paper, we propose a novel distributed, adaptive control algorithm that maximizes weighted throughput while ensuring stable operation in the face of highly bursty workloads. Our algorithm is designed to meet the challenges of extreme-scale stream processing systems, where overprovisioning is not an option, by making the best use of resources even when the proffered load is greater than available resources. We have implemented our algorithm in a real-world distributed stream processing system and a simulation environment. Our results show that our algorithm is not only self-stabilizing and robust to errors, but also outperforms traditional approaches over a broad range of buffer sizes, processing graphs, and burstiness types and levels.

This paper presents a multiple description (MD) video codec based on the principles side-information coding. In particular, we highlight certain key components of the codec design that contribute significantly to the rate-distortion performance of the proposed codec. These include the use of randomized permutations of the quantization codebook in conjunction with binary LDPC codes for partitioning the available bit-rate among the coefficient bit-planes. Another key component of the proposed codec is the use of pdf estimation for improved decoder reconstruction. Lastly, we use a bank of sequential LDPC decoders to efficiently decode the transmitted coset information. Empirical evaluation demonstrates the superior performance of the proposed codec for the communication of encoded video over packet erasure channels.

This paper presents a distortion optimized streaming algorithm for on-demand streaming of multimedia. Given the pre-encoded packets of a multimedia stream, we propose a fast algorithm for selecting an appropriate subset of these packets such that the overall client distortion is minimized. This minimization is performed within the rate constraints imposed by the communication channel. In particular, at each transmission opportunity, the proposed approach uses a linear-time algorithm to select the best packet to transmit through the minimization of the expected client distortion. The time complexity of the algorithm is reduced through a factorization of the streaming policy into simpler terms and performing a greedy optimization to select the packet. Inevitably, this in itself leads to sub-optimal results. To alleviate the adverse impact of the greedy optimization, the cost function is penalized with the expected buffer occupancy at the end of the epoch of the optimization. We pose this problem as a Lagrangian minimization. We demonstrate the efficacy of the proposed approach through empirical evaluation.

This paper addresses the problem of video coding in a joint source-channel setting. In particular, we propose a video encoding algorithm that prevents the indefinite propagation of errors in predictively encoded video-a problem that has received considerable attention over the last decade. This is accomplished by periodically transmitting a small amount of additional information, termed coset information, to the decoder, as opposed to the popular approach of periodic insertion of intra-coded frames. Perhaps surprisingly, the coset information is capable of correcting for errors, without the encoder having a precise knowledge of the lost packets that resulted in the errors. In the context of real-time transmission, the proposed approach entails a minimal loss in performance over conventional encoding in the absence of channel losses, while simultaneously allowing error recovery in the event of channel losses. We demonstrate the efficacy of the proposed approach through experimental evaluation. In particular, the performance of the proposed framework is 3-4 dB superior to the conventional approach of periodic insertion of intra-coded frames, and 1.5-2 dB away from an ideal system, with infinite decoding delay, operating at Shannon capacity.

The problem of robust communication of predictive encoded video in a joint source-channel setting is addressed. Specifically, the problem of predictive mismatch, where there is a drift between the state of the encoder and the decoder is addressed as a variant of the Wyner-Ziv problem. A video encoding algorithm based on the H.26L video codec, which presents the propagation of error in predictively encoded video in the event of predictive mismatch (or drift) between the encoder and the decoder, is proposed. One of the main advantages of the proposed approach is that there is minimal loss in performance over the standard H.26L encoder during error-free transmission, while simultaneously allowing error recovery in the event of errors. Using turbo codes as coset codes, the performance of the proposed codec is evaluated and the efficacy of the proposed framework is demonstrated. The performance of the proposed approach can only improve with the use of superior coset codes.

A commonly encountered problem in the communication of predictively encoded video is that of predictive mismatch or drift. The problem of predictive mismatch manifests itself in numerous communication scenarios, including on-demand streaming, real-time streaming and multicast streaming. This paper proposes a state-free video encoding architecture that alleviates this problem. The main benefit of state-free encoding is that there is no need for the encoder and the decoder to maintain the same state, or equivalently, predict using the same predictor. This facilitates robust communication of causally encoded media. The proposed approach is based on the Wyner-Ziv theorem in information theory. Consequently, it leverages the superior performance of coset codes for the Wyner-Ziv problem for predictive coding. A video codec, with state-free functionality, based on the H.26L encoding standard is proposed. The performance of the proposed codec is within 1-2.5 dB of the H.26L encoder.

The main hindrance to the development of efficient low-latency multiple description (MD) video coders are the problem of predictive mismatch. In this paper, we present a two-channel predictive MD video codec architecture based on the recently proposed WYZE-PMD framework. The proposed codec transmits coset information to curtail error-propagation caused by predictive mismatch, without requiring high latency or restrictive channel assumptions. MD scalar quantizers are used to generate multiple descriptions, low-density parity check (LDPC) codes are used to generate coset information, and the H.263 video coding standard is used for efficient motion compensation. The proposed codec is used to code descriptions of CIF video for communication over two erasure channels with independent failure probabilities. Results indicate that the proposed codec provides efficient, drift-free predictive MD coding.

The inherently causal nature of conventional single-pass error diffusion (ED) halftoning results in asymmetric diffusion of error. This results in the introduction of directional artifacts in the output halftone. In this paper we propose a novel two-pass algorithm which achieves symmetric error diffusion by using a zero-phase signal transfer function. We determine conditions under which isotropic diffusion of error and noise suppression are achieved. Experimental results demonstrate that the proposed algorithm breaks up worms and randomizes their direction, thus making the output halftone more visually appealing as compared to conventional error diffusion.

Caching of Internet content in caches local to users is beneficial to both users and the network, because it reduces retrieval times for the user as well as reduces load on the network. However, it comes at the cost of storage in the cache, which can be large, particularly when multimedia objects are cached. In this paper, we address the problem of caching multimedia objects such as audio and video streams, in a cost-distortion optimized way. That is, we seek caching policies that minimize the cost of both storage and transmission while minimizing the distortion seen by the user (or equivalently, maximizing the quality seen by the user). Simulation results demonstrate that caching in a cost-distortion optimized manner leads to significant improvements over the case where no caching is performed.

Predictive encoding with respect to multiple possible predictors is a common scenario encountered in many digital set-top box applications, such as redundant storage of video/audio data, real-time robust communication with peripherals and Internet video/audio telephony. A key problem associated with this scenario is that of predictive mismatch or drift. In the present paper, we pose the problem of predictive encoding with multiple possible predictors as a variant of the well-known Wyner-Ziv side-information problem. We propose an approach based on the use of coset codes for predictive encoding, for mitigating the effect of drift without overly sacrificing compression efficiency. The proposed approach can be used to improve coding performance in a wide range of practical applications such as multiple description coding, scalable coding and redundant storage of video/audio streams. We illustrate the efficacy of the proposed approach through a simple example based on the application of low-delay Internet telephony. Our results indicate that the proposed approach significantly outperforms conventional predictive encoding for communication over lossy channels.

We address the problem of multimedia streaming over DiffServ networks that offer various qualities of service (QoS) at different price points. In particular, we seek cost-distortion optimized transmission policies that minimize the distortion seen by the client under a cost constraint. Our results show that for on-demand streaming of stored media, DiffServ networks provide little or no gain over networks that offers only a single, cost-effective, QoS. However, for real-time conversational communication or multicast streaming, optimized transmission over DiffServ networks can perform better than optimized transmission over any single QoS by over 2 dB at the same cost.

A novel solution to the problem of data embedding in images is proposed in this paper The proposed algorithm allows high capacity data embedding and is robust to JPEG image compression data is embedded in the wavelet domain which provides better perceptual masking compared to the DCT domain set partitioning in hierarchical trees (SPIHT) is used to control the distortion (in the sense of PSNR) in the embedded host. Unlike other data embedding algorithms available in literature, the proposed algorithm provides control over the BER of the embedded data by appropriately choosing the JPEG quantization matrix. Preliminary results of an implementation of the algorithm are also presented.