Database Reference
In-Depth Information
4
Mining Data Streams
Most of the algorithms described in this topic assume that we are mining a database. That
is, all our data is available when and if we want it. In this chapter, we shall make another
assumption: data arrives in a stream or streams, and if it is not processed immediately or
stored, then it is lost forever. Moreover, we shall assume that the data arrives so rapidly that
it is not feasible to store it all in active storage (i.e., in a conventional database), and then
interact with it at the time of our choosing.
The algorithms for processing streams each involve summarization of the stream in some
way. We shall start by considering how to make a useful sample of a stream and how to filter
a stream to eliminate most of the “undesirable” elements. We then show how to estimate the
number of different elements in a stream using much less storage than would be required if
we listed all the elements we have seen.
Another approach to summarizing a stream is to look at only a fixed-length “window”
consisting of the last
n
elements for some (typically large)
n
. We then query the window
as if it were a relation in a database. If there are many streams and/or
n
is large, we may
not be able to store the entire window for every stream, so we need to summarize even the
windows. We address the fundamental problem of maintaining an approximate count on the
number of 1s in the window of a bit stream, while using much less space than would be
needed to store the entire window itself. This technique generalizes to approximating vari-
ous kinds of sums.
4.1 The Stream Data Model
Let us begin by discussing the elements of streams and stream processing. We explain the
difference between streams and databases and the special problems that arise when dealing
with streams. Some typical applications where the stream model applies will be examined.
