Project Leader

Alin Dobra is the project leader and the PI of the NSF grant supporting the project.

Team Members

• Kavita Methora

  Kavita worked on extending the approximation techniques for sketches to Top-k problems (both exact and probabilistic). Her work resulted in an efficient solution to the top-k problem for very large databases.

  Kavita is now a software engineer at Amazon

• Lixia Chen

  The uncertainity in probabilistic databases can be treated mathematically similarly to the uncertainity in approximation techniques. In her thesis, Lixia extended the analysis of approximation techniques to the analysis of aggregates in probabilistic databases.

  Lixia has joined Amazon

• Florin Rusu

  Florin's work deals with sketch based approximation techniques applied to approximating queries over streaming data. Florin solved a nubmer of fundamental issues with sketch based approximation including: type of random number generator to use for sketching, a full characterization of hash-sketches and combining sketching and sampling.

  As a direct results of the work supported by this grant, Florin was employed as an Assistant Professor at University of California, Merceed in September 2010.

• Amit Dhurandhar

  Amit's work extends the analysis and techniques developed for approximation techniques to statistical analysis of classification methods. In particular, Amit made significant progress in a small sample theory characterization of learning methods. This theory explains, for example, the cross-validation behavior of various classifiers with an analytic method.

  Amit's work as part of this project lead to his employment as a Research Scientist at IBM's T.J. Watson lab.

• Laukik Chitnis

  In his work Laukik investigated how aggregate queries can be performed, in an approximate manner, in sensor networks. A nubmer of fundamental results were obtained as part of this work, including a general solution for approximate aggregate processing in sensor and limits on precision based on failure rate of sensor networks.

  Laukik joined the Web Search team at Yahoo! upon graduation and latter moved to Google.

• Guruditta Golani

  Guruditta's work provided theoretical infrastructure to extend any data-streaming algorithm into a distributed algorithm by exploiting the underlying linear structure. This resulted in fundamental results that shaped later developments in this project.