Frequent items detection is a very useful technique in many applications, such as network monitor, network intrusion detection, worm virus detection, and so on, where data is generally uncertain and could be described using probability. While having been studied intensively in the field of deterministic data, frequent items detection is still novel in the emerging uncertain data field. In this paper, we study the semantic of frequent items detection on uncertain data stream and present a new definition of frequent items over sliding window. Based on the definition, an efficient algorithm is proposed to detect frequent items on uncertain data stream. The algorithm finds the recursion rule in probability computation and greatly improves the efficiency of single data detection, and dynamically detects recent m elements incrementally. Finally, detailed analysis and thorough experimental results demonstrate the efficiency and scalability of our approach.
