Design and analysis of algorithms for streaming data

Abstract

Streaming algorithms have always gained attention of researchers due to the chal lenges it o ers. Today, when the data systems are progressively transforming into streaming system and everything is computed in real time, it becomes very impor tant to make the fundamental mathematical tools adaptive to them. This research is strongly motivated by the complexity of handling such systems. The purpose of this research is to intelligently modify the conventional algorithms so that it can process data streams e ciently. We had certain questions in mind before considering any algorithm such as: 1) Can we convert this algorithm to online version? If yes, whats the minimal informa tion we must store to compute things in streaming manner ? If no, Can we somehow make it approximation or updating algorithm? 2) What are the parameters that can be obtained sequentially ? 3) Are there any existing solutions available? If yes, how they can be improved? Following the approach we rst began with optimization problems. We reviewed online version of Least Squares Regression, Mean Squared Error, Principal Component Analysis and Principal Component Regression. Apart from this, we explored matrix decomposition techniques such as Eigenvalue Decomposition and Singular Value Decomposition. We speci cally focused on the problems of updating SVD of modi ed matrices. In the course of which we came across SVD of rank-1 modi ed matrices. We noticed that when SVD of a rank-1 perturbed matrix is updated, singular vectors computation requires Cauchy matrix vector product. With this observation, in this thesis we present an e cient method based on Fast Multipole Method (FMM) for updating singular vectors in O(n log(1)) time. Where, is the precision of computation. Further, we present a method for updating SVD of rank-1 perturbed matrices in O(n2 log(1)) time.