Papers for Presentations

·       How to Summarize the Universe: Dynamic Maintenance of Quantiles

   Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss (AT&T Labs - Research, U.S.A.). VLDB  2002

·       Distributed streams algorithms for sliding windows

  P. Gibbons, S. Tirthapura, SPAA'02



Flip Korn, S. Muthukrishnan, Divesh Srivastava (AT&T Labs - Research, U.S.A.), VLDB 2002.



Graham Cormode, S. Muthukrishnan (2002)


Mayur Datar, S Muthukrishnan (2002)

·        Fast Algorithms For Hierarchical Range Histogram Construction

      N. Koudas, D. Srivastava, Sudipto  ACM-PODS Principles of Database Systems, 2002

·        Maintaining Stream Statistics over Sliding Windows

M. Datar, A. Gionis and R. Motwani, Sudipto, 13th Symposium on Discrete Algorithms (SODA), 2002.

·        Comparing top k lists

R. Fagin, R. Kumar, and D. Sivakumar. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003.

·        Distributed Top-K Monitoring with Adjustable Error Guarantees

Babcock, Brian; Olston, Chris

·        Rangesum Histograms

Muthukrishnan S, AT&T Research and Rutgers University; Martin Strauss, AT&T Labs (SODA), 2003

·        Space-Efficient Finger Search on Degree-Balanced Search Trees

Guy Blelloch, Bruce M. Maggs, Shan Leung Maverick Woo, Carnegie Mellon University (SODA) 2003

·        Lower Bounds for External Memory Dictionaries

Gerth Stølting Brodal, Rolf Fagerberg, BRICS, Aarhus University

·        Progressive Merge Join: A Generic and Non-blocking Sort-based Join Algorithm

Jens-Peter Dittrich, Bernhard Seeger (University of Marburg, Germany), David Scot Taylor, Peter Widmayer (Swiss Federal Institute of Technology (ETHZ), Switzerland), VLDB 2002.


Surveys (not for presentations)

·        External Memory Algorithms

Jeffrey Scott Vitter

1998. Full Version.

·        Synopsis data structures for massive data sets

P.B. Gibbons and Y. Matias.

DIMACS Series in Discrete Mathematics and Theoretical Computer Science.

A two-page summary  in SODA'99.

·        The New Jersey Data Reduction Report.

D. Barbara, W. Dumouchel, C. Faloutsos, P.J. Haas, J.M. Hellerstein, Y. Ioannidis, H.V. Jagadish, T. Johnson, R. Ng, V. Poosala, K.A. Ross, and K.S. Sevcik.

Bulletin of the Technical Committee on Data Engineering, December 1997.


·        Models and Issues in Data Stream Systems


Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer,

Proceedings of 21st ACM Symposium on Principles of Database Systems (PODS 2002)


Return to seminar home page

For requests or corrections contact

Last updated February 2003