Title: "Finding Frequent Items in Data Streams"
Speaker: Alexander Loukissas (UCSD)

Recently there has emerged a new class of data-intensive applications, 
in which the data is best modelled as continuous, time-varying data streams, 
instead of persistent relations. Examples of such applications include sensor 
networks, financial tickers, web applications, etc. One of the important 
statistics in this data stream scenario is the knowledge of which items appear
 many times (more frequently or more than threshold). This knowledge is useful
 in many contexts, such as selectivity estimation, network management, data 
mining, etc. Because data streams are potentially infinite in size and have 
arbitrarily high data rate, it becomes infeasible to answer such queries using
 a full histogram, since for many data sets this requires space linear in the 
size of the data set. This introduces the need for approximation, using data 
synopsis structures, which have small memory footprint and which can also 
produce fast, high-quality answers. This talk will focus on presenting an 
overview of most of the algorithms that address this problem. We will discuss 
the basic idea behind each algorithm and we will present our experimental 
results for each one.