Distributed On-Demand Video Content Distribution

We present a multi-channel Video-on-Demand (VoD) system using ``plug-and-play" helpers. Helpers are heterogenous ``micro-servers"with limited storage, bandwidth and number of users they can serve simultaneously. Our proposed system has the following salient features: (1) it minimizes load on centralized infrastructure; (2) it is distributed and requires little or no maintenance overhead; and (3) it is adaptable to varying supply and demand patterns across multiple video channels irrespective of video popularity. Our proposed solution jointly optimizes over helper-user topology, video storage allocation and bandwidth allocation. The combinatorial nature of the problem and the system demand for distributed algorithms makes the problem uniquely challenging. By utilizing Lagrangian decomposition and Markov chain approximation based arguments, we address this challenge by designing two distributed algorithms running in tandem: a primal-dual storage and bandwidth allocation algorithm and a ``soft-worst-neighbor-choking" topology-building algorithm. Our scheme provably converges to a near-optimal solution, and is easy to implement in practice. Simulation results validate that the proposed scheme achieves minimum sever load under highly heterogeneous combinations of supply and demand patterns, and is robust to system dynamics of user/helper churn, user/helper asynchrony, and random delays in the network. [paper] [slides]

 

Frame-Bufferless Sum-Rate Constrained Video Encoding Using Feedback

We investigate the design of a frame-bufferless and low-latency video communication system, where the encoder has no access to any previous frames and only one use of feedback communication from the decoder to the encoder is allowed in encoding each frame. This strict requirement of encoder complexity and system latency is of critical importance in designing low complexity realtime video communication systems where the encoder is limited in storage and computing resources and the use of the feedback channel must not incur accumulated receiver playback delay. We propose a simple online statistical model that captures the time-varying video process and develop a general framework that explores how to best utilize the feedback and distributed source coding mechanisms to minimize the overall communication rate. Our analysis and experimental results validate the efficiency of the proposed system and highlight its potential in practical system design. [paper] [slides]

 

 

 

 

 

 

VSYNC --- A Novel Video File Synchronization Protocol (demo1, demo2)

VSYNC is a novel incremental video file synchronization system that efficiently synchronizes two video files at remote ends through a bi-directional communications link. Retransmission of a video file that has been modified only slightly, for the purpose of synchronization with a remote-end copy, is extremely expensive but avoidable. VSYNC is a bi-directional algorithm designed to automatically detect and transmit changes in the modified video file without the knowledge of what was changed. Another feature of VSYNC is that it allows synchronization to within some user defined distortion constraint. A hierarchical hashing scheme is designed to compare video chunks, converting the high-level content information to a low-level hash stream that is more amenable to the tools of coding theory. Our approach shows impressive gains in transmission rate-savings. In a typical example of two 12 sec video files with about 10% of the frames being edited, transmission savings of 44% to 87% can be obtained compared to directly sending the updated video files using H.264 and rsync. [paper] [slides]

Collaborative Filtering for the Netflix Prize

Designed an iterative collaborative filtering approach to solve for the Netflix Prize Challenge. Collaborative filtering based recommendation systems is widely deployed in many commercial systems as in Amazon, Google News, and etc. In most cases the goal is to predict user preferences on items by learning their aggregated relationships through the historical records. An accurate recommendation system is crucial for these companies to facilitate user interactions through online communities. Among most collaborative filtering approaches, the major two challenges are usually scalability and sparseness. It is shown in the results that we are able to gain a 2.3% improvement over the commercial Cinematch recommendation system deployed by Netflix, even without any preprocessing of the training data. [paper] [slides]

 

HMM Based Video Classication Using Simple Features

Content-based video search has attracted much attention recently. It has wide applications in many areas such as automatic video tagging, personal video archive, video surveillance and etc. In this work, we aim to classify sports videos. Each video is represented by a sequence of frames. Simple features of two dimensions are extracted from each frame and are used as observations in an HMM chain. Two techniques respectively using Gaussian mixtures and kernel density estimates as emission probabilities are used for comparisons. Experiments using a training database of 20 videos in 4 classes show 100% classication rate over 20 test videos, with HMM-KDE outperforming HMM-GM. All videos are unprocessed raw videos from YouTube. [paper] [slides]

 

Image Compression via Bayesian Compressed Sensing

In this work finding sparse representations in a set of overcomplete bases is studied using matching pursuits (MP), basis pursuits (BP) and sparse Bayesian learning (SBL) and is applied to image compression. The sparsity of the solutions obtained under these algorithms is compared with different reconstruction PSNRs. A set of images are tested and it is concluded that SBL outperforms the other algorithms in terms of its ability to find solutions that are more sparse given a defined overcomplete dictionary. Images are represented in the discrete cosine transformation (DCT) domain and are quantized and coded. Results show that the PSNR under same bit rate from SBL outperforms that obtained under other techniques and in some regions surpass standard complete DCT techniques. [paper] [slides]

 

Support Vector Machines versus Boosting

Support Vector Machines (SVMs) and Adaptive Boosting (AdaBoost) are two successful classification methods. They are essentially the same as they both try to maximize the minimal margin on a training set. In this work, we present an even platform to compare these two learning algorithms in terms of their test error, margin distribution and generalization power. Two basic models of polynomials and decision stumps are used to evaluate eight real-world binary datasets. We concluded that the generalization power of AdaBoost with linear SVMs as base learners and that of SVMs with decision stumps as kernels outperform other scenarios. Although the training error of AdaBoost approaches to zero with the increase number of weak learners, its test error starts to rise at a certain step. For both SVMs and AdaBoost, the cumulative margin distribution is indicative of the test error. [paper] [slides]