In recent years, a new class of applications has come to the forefront { p- marily due to the advancement in our ability to collect data from multitudes of devices, and process them e ciently. These include homeland security - plications, sensor/pervasive computing applications, various kinds of mo- toring applications, and even traditional applications belonging to nancial, computer network management, and telecommunication domains. These - plications need to process data continuously (and as long as data is available) from one or more sources. The sequence of data items continuously gen- ated by sources is termed a data stream. Because of the possible never-ending nature of a data stream, the amount of data to be processed is likely to be unbounded. In addition, timely detection of interesting changes or patterns or aggregations over incoming data is critical for many of these applications. Furthermore, the data arrival rates may uctuate over a period of time and may be bursty at times. For most of these applications, Quality of Service (or QoS) requirements, such as response time, memory usage, and throughput are extremely important. These application requirements make it infeasible to simply load the incoming data streams into a persistent store and process them e ectively using currently available database management techniques.