Sliding-Window Top-k Pattern Mining on Uncertain Streams
Zhenjie Zhang, Yadong Zhang · 2011
Uncertainty pervades many application fields such as sensor network and mobile data management. In these fields, uncertain data items often arrive rapidly and need to be handled in a streaming fashion. The key challenge of processing uncertain streams stems from the limited memory and the CPU resource of handling both arriving and expiring windows in the high-rate streams, combined with the difficulty of coping with the dilemma caused by error parameter e. Setting e too high may obtain inaccurate results while setting it too low will make memory consumption large. In order to deal with the challenges, this paper focuses on finding the Top-k Patterns on uncertain streams, and based on the sliding window model and Chernoff Bound technology proposes a space- and time-efficient algorithm, called Topk-PU, in which an increasing expected support function is designed to approximately calculate the count of each pattern. Experimental results show that the fast processing rate, and the efficiency of our proposed algorithm.