Frequent Item Detection on Probabilistic Data

Frequent items detection is one of the valuable techniques in many applications, such as network monitor, network intrusion detection, worm virus detection, and so on. This technique has been well studied on deterministic databases. However, it is a new task on emerging uncertain database. In this paper, a new definition of frequent items detection on uncertain data is defined. Based on it, two efficient filtering rules are proposed, which can largely reduce the number of items to be detected. Furthermore, an efficient algorithm UFI is proposed to detect frequent items on uncertain database. The UFI algorithm adopts the recursion rule in probability computation and greatly improves the efficiency of single data detection. Finally, the experimental results show that the proposed approaches can efficiently prune the candidates, reduce the corresponding searching space and improve the performance of query processing on uncertain data.