ALBERT

Description:    Data uncertainty is inherent in many real-world applications such as sensor monitoring systems, location-based services, and medical diagnostic systems. Moreover, many real-world applications are now capable of producing continuous, unbounded data streams. During the recent years, new methods have been developed to find frequent patterns in uncertain databases; nevertheless, very limited work has been done in discovering frequent patterns in uncertain data streams. The current solutions for frequent pattern mining in uncertain streams take a FP-tree-based approach; however, recent studies have shown that FP-tree-based algorithms do not perform well in the presence of data uncertainty. In this paper, we propose two hyper-structure-based false-positive-oriented algorithms to efficiently mine frequent itemsets from streams of uncertain data. The first algorithm, UHS-Stream, is designed to find all frequent itemsets up to the current moment. The second algorithm, TFUHS-Stream, is designed to find frequent itemsets in an uncertain data stream in a time-fading manner. Experimental results show that the proposed hyper-structure-based algorithms outperform the existing tree-based algorithms in terms of accuracy, runtime, and memory usage. Content Type Journal Article Category Regular Paper Pages 1-26 DOI 10.1007/s10115-012-0581-y Authors Chandima HewaNadungodage, Department of Computer and Information Science, Indiana University—Purdue University Indianapolis, 723 West Michigan Street, Indianapolis, IN 46202-5132, USA Yuni Xia, Department of Computer and Information Science, Indiana University—Purdue University Indianapolis, 723 West Michigan Street, Indianapolis, IN 46202-5132, USA Jaehwan John Lee, Department of Electrical and Computer Engineering, Indiana University—Purdue University Indianapolis, 723 West Michigan Street, Indianapolis, IN 46202-5132, USA Yi-cheng Tu, Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, FL 33620, USA Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377