PROCESSING DATA STREAMS Andrew ... - Semantic Scholar

Sketchability: A fundamental problem in the data-stream model is to compare ..... network monitoring applications, any algorithm will be limited to a single pass ...
995KB Sizes 2 Downloads 213 Views
PROCESSING DATA STREAMS Andrew McGregor A DISSERTATION

in

Computer and Information Science

Presented to the Faculties of the University of Pennsylvania in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

2007

Sampath Kannan Supervisor of Dissertation

Rajeev Alur Graduate Group Chairperson

COPYRIGHT Andrew McGregor 2007

Acknowledgements I am fortunate to have learnt a lot from some great people during my time in graduate school. First and foremost, I would like to thank Sampath Kannan for being a fantastic advisor. Talking with Sampath was always a pleasure and I can only hope that I have picked up some of his great taste in choosing problems. I am also very grateful to Sasha Barg, Sudipto Guha, and Bruce Shepherd for additional mentoring over the last five years. Working with Sudipto was a lot of fun, especially when our opinions diverged and caffeine-fueled hours would be spent in a back-andforth of conjectures and counter-examples until a perfectly-formed theorem would emerge! During four internships at DIMACS and Bell Labs, Sasha convinced me of the benefits of thinking geometrically about coding theory and Bruce taught me not to fear case-analysis in combinatorial optimization. All have been a tremendous source of advice and encouragement. A big thank you to the wonderful people of the St. Andrew’s Society of the State of New York for the scholarship that partially funded my first year at Penn. I would like to thank Sudipto Guha, Piotr Indyk, Michael Kearns, and Sanjeev Khanna for agreeing to be on my thesis committee. Thanks for your time and suggestions, and a special thanks to Piotr for waking up at 4 a.m. to make my defense after a day of travel upsets. Also, no thesis would ever be completed in Penn C.I.S. without the help of the indomitable Mike Felker, the department’s paper-work tsar. Thank you for making the administrative side of things run so smoothly. I am a firm believer that the best way to grow as a researcher is to collaborate iii

with smart, enthusiastic people. I am fortunate to have had the opportunity to work with co-authors that fit that bill: Deepak, Stan, Sasha, Tu˘gkan, Amit, Matthew, Graham, Joan, Peter, Boulos, Piotr, Sampath, Sanjeev, Keshav, Eduardo, Muthu, Jeff, Bruce, Sid, Suresh, Jian, and Zhengyuan. Equally important to me has been the theory students at Penn: Stan, Milan, Yael, Boulos, Niel, Kuku, Sid, Mirko, and the ill-fated theory fish, Turing. Keep watering the plants and take care of Gollum! Research has its moments of both frustration and utter elation. It is also addictive to the point of requiring “interventions” once in a while. For these I’d like to thank the “normal” people in my life, the people who distinguish between offices and coffee shops (thanks to Intermezzo and Capriccio) and who remain unconvinced that “Let ǫ < 0” is the world’s funniest joke. To old friends from the UK who dragged me to far-flung destinations or came out to visit (including my awesome sister), thanks for ensuring that America became a second home, rather than just a new home. (For specific instances of having a roof over my head, I would like to thank Ewan and Rachel, Simon and Rashmin, the Barg family, the Fraser family, Nick, Helen, David and Laura, Graham and Valentine, and the inhabitants of the inimitable 19 Frank’s Lane. Thanks for letting me cover your kitchen tables with papers and I promise to replenish your coffee jars at the earliest opportunity!) To newer friends in the States with whom I explored the bizarre world that is graduate school: Stan, Vlad, Monica, Ilinca, Ryan, Tania, Anne, Kilian, Ameesh, Sasha, Niel, Nikhil (thanks for printing this thing!), Nick, Hanna, Sloop, and especially Christie, I owe you all a lot. Thank you. This thesis is dedicated to my mum and dad, Hilary and Robert. Thank you for the belief you have in me and for not objecting too much when I decided study in the States. I never doubted that I would be finishing t