DIMACS Theoretical Computer Science Seminar

Title: Metric Embeddings in Data Stream Algorithms

Speaker: S. Muthukrishnan, DIMACS, Rutgers University

Date: September 15, 2003 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

 There is a rich theory of metric space embeddings; these methods 
    are now being applied to algorithms for handling super-fast data 
    streams.  I will describe three such applications in spaces that 
    deal with
        vector distances
        tree and string distances, and
        spatial orientations.

    These are amongst the most general and powerful results known in 
    data stream algorithms, but, yes, there is a coda.