Tracking the Frequency Moments at All Times

MPhil Thesis Defence


Title: "Tracking the Frequency Moments at All Times"

By

Mr. Wai Ming TAI


Abstract

The traditional requirement for a randomized streaming algorithm is just 
one-shot, i.e., algorithm should be correct (within the stated ε-error bound)
at the end of the stream. In this paper, we study the tracking problem, where 
the output should be correct at all times. The standard approach for solving 
the tracking problem is to run O(log m) independent instances of the one-shot 
algorithm and apply the union bound to all m time instances. In this paper, we 
study if this standard approach can be improved, for the classical frequency 
moment problem. We show that for the Fp problem for any 1 < p ≤ 2, we actually 
only need O(log log m + log n) copies to achieve the tracking guarantee in the 
cash register model, where n is the universe size. Meanwhile, we present a 
lower bound of Ω(log m log log m) bits for all linear sketches achieving this 
guarantee. This shows that our upper bound is tight when n=(log m)O(1). We 
also present an Ω(log2 m) lower bound in the turnstile model, showing that the 
standard approach by using the union bound is essentially optimal.


Date:			Tuesday, 23 June 2015

Time:			3:00pm - 5:00pm

Venue:			Room 2132B
 			Lift 19

Committee Members:	Dr. Ke Yi (Supervisor)
 			Prof. Mordecai Golin (Chairperson)
 			Dr. Sunil Arya


**** ALL are Welcome ****