Abstract
In many real world applications, such as monitoring in sensor networks, online TV ratings, and DoS (deny of service) attack detection, information delivering is by the form of data streams. Differs from the traditional database systems, data streams have the following characteristics: (1) total amount of data is enormous, much more than traditional database systems or memory device (e.g. hard disk) can afford; (2) highly updating rate; (3) rather than one-time query, users tend to issue sort of continuous query instead. These differences make it difficult to calculate the statistics of data streams. In this thesis, a method to disclose frequent items in masses of data streams is proposed. Frequent items refer to those whose occurrence rates exceed a given frequency threshold, which can be specified by inquirers. In order to meet the characteristics of data stream processing and without losing the practicability, the proposed approach has the following objectives: (1) any query interval: Given a time period within the system-affordable range, the frequent items of this period will be responded efficiently; (2) distributed processing: the approach can separately prune away many occurrences from bottom to top without losing any fidelity; (3) storage saving: due to the enormous amount of occurrences, we have to design a mechanism to conserve the potential frequent items using only limited local counters; (4) computation saving: because of the highly updating rate, the proposed approach should be able to respond the statistical results of frequent items without delay. We proposed a distributed algorithm which fulfills the above requirements in this thesis as well as proved its correctness when frequent items do exist. To demonstrate the practicability in locating the proper frequent items we conduct some simulations, the experimental results show that most of the items generated are of eminent occurrence rates even though the frequent items are eccentric.