Data Streams, Dyck Languages, and Detecting Dubious Data Structures
February 17, 2011
JEC 3117 - 4:00 p.m. to 5:00 p.m.
You are watching an interaction with a priority queue: at each step the user either inserts a new value into the queue or asks for the current minimum to be extracted. However, you're suspicious that the priority queue may not always be extracting the correct minimum. Can you help the user recognize when this happens without having to remember all the values she has inserted?
The above is an example of a problem in the data stream model where the input is a long stream of data and the goal is to compute properties of the input while only using memory that is sub-linear in the length of the stream. This theoretical model has become increasingly popular over the last decade. Its original motivation stems from applications such as monitoring network traffic, processing massive data sets, and aggregation in sensor networks. In this talk, we will present recent results on recognizing formal languages. We'll start with some algorithms for memory checking and then discuss connections with other problems.
Includes joint work with Amit Chakrabarti, Graham Cormode, and Ranganath Kondapally.
Andrew McGregor is an assistant professor at the University of Massachusetts, Amherst. Prior to this he was a postdoctoral researcher at Microsoft Research and the Information Theory and Applications Center at UCSD. His main research area is theoretical computer science, particular problems that relate to processing massive data sets and streams. In 2007, he received his Ph.D. from the University of Pennsylvania. He received the NSF Career award in 2010.
Hosted by: Dr. Elliot Anshelevich (x6491)
Last updated: February 1, 2011