Data Streaming: Algorithms & Systems





Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy


Course Contents

Motivating applications: network monitoring, sensor networks, need for highly efficient processing of high speed and high volume data streams, Space and time efficient randomized algorithms as a candidate solution, models of data streams. Basics of randomization: elementary probability theory, expectation, linearity of expectation, variance, Markov and Chebychevs inequality, Chernoff and Hoeffding (CH) tail inequalities, hash functions, limited independence, CH bounds for limited independence. Finding frequent items in data streams, Estimating distinct item queries, Estimating frequency moments, estimating join sizes, Approximate histograms over data streams, Transforms over data streams, wavelets, Fourier and DCT clustering over data streams, Applications to graphs. 


Number of sections:

Tutors for each section:

Schedule for Lectures:

Schedule for Tutorial:

Schedule for Labs:



Birds at IIT Kanpur
Information for School Children
IITK Radio
Counseling Service