Research on Data Stream Algorithms

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Title: "Research on Data Stream Algorithms"

by

WANG, Xiao

Abstract

Big data problem, characterized by high volume, high velocity and high 
variety, has become one of the most common problems in the Computer 
Science field. The data is always too big and fast to be stored while we 
only have one pass of the data. Data stream algorithms view data as a 
stream and use very small working memory, which is usually 
poly-logarithmic to the data size.

In this project, we investigated the state-of-the-art techniques for data 
stream algorithms and proposed a new problem that generalize existing 
problems: computing any frequency moments on any ranges. We also designed 
a general algorithm that takes small space and update time. For the case 
of 0-th and 2-nd frequency moment, this algorithm takes far less time to 
update {O(\log \log U)}, making it more suitable for high speed data.

Date            :       4 May 2013 (Sat)

Time            :       10:50am to 11:40am

Venue           :       3416

Advisor         :       Prof. Ke YI

2nd Reader      :       Prof. Cunsheng DING