tailieunhanh - Data Streams Models and Algorithms- P2

Data Streams Models and Algorithms- P2: In recent years, the progress in hardware technology has made it possible for organizations to store and record large streams of transactional data. Such data sets which continuously and rapidly grow over time are referred to as data streams. In addition, the development of sensor technology has resulted in the possibility of monitoring many events in real time. | 14 DATA STREAMS MODELSAND ALGORITHMS beginning of the stream. The order of a particular class of snapshots define the level of granularity in time at which the snapshots are maintained. The snapshots of different order are maintained as follows Snapshots of the -th order occur at time intervals of a1 where a is an integer and a 1. Specifically each snapshot of the -th order is taken at a moment in time when the clock value1 from the beginning of the stream is exactly divisible by a1. At any given moment in time only the last a 1 snapshots of order i are stored. We note that the above definition allows for considerable redundancy in storage of snapshots. For example the clock time of 8 is divisible by 2 21 22 and 23 where a 2 . Therefore the state of the micro-clusters at a clock time of 8 simultaneously corresponds to order 0 order 1 order 2 and order 3 snapshots. From an implementation point of view a snapshot needs to be maintained only once. We make the following observations For a data stream the maximum order of any snapshot stored at T time units since the beginning of the stream mining process is loga T . For a data stream the maximum number of snapshots maintained at T time units since the beginning of the stream mining process is a 1 loga T . For any user specified time window of h at least one stored snapshot can be found within 2 h units of the current time. While the first two results are quite easy to see the last one needs to be proven formally. LEMMA Let hbea user-specified time window tc be the current time and ts be the time of the last stored snapshot ofany orderjust before the time tc h. Then tc ts 2 h. Proof Let r be the smallest integer such that ar h. Therefore we know that ar 1 h. Since we know that there are a 1 snapshots of order r 1 at least one snapshot of order r 1 must always exist before tc h. Let ts be the snapshot of order r 1 which occurs just before tc h. Then tc h ts ar 1. Therefore we have tc ts h ar 1 2 h. Thus in this case