A sliding window-based false-negative approach for ubiquitous data stream analysis

作者：Kim Younghee^*; Park Doo Soon; Kim Heewan; Kim Ungmo

来源：International Journal of Communication Systems, 2012, 25(6): 691-716.

DOI：10.1002/dac.1211

• ubiquitous data stream mining
• false negative
• frequent itemsets
• Chernoff bound
• approximate counts

Ubiquitous data stream mining (UDSM) is the process of performing data analysis on mobile, embedded and ubiquitous devices. In many cases, a large volume of data can be mined for interesting and relevant information in a wide variety of applications. Data stream mining requires computationally intensive mining techniques to be applied in mobile environments constrained by analysis of a real-time single pass with limited computational resources. Therefore, we have to ensure that the result is within the error tolerance range. In this paper, we suggest a method for a false-negative approach based on the Chernoff bound for efficient analysis of the data stream. Hence, we consider the problem of approximating frequency counts for space-efficient computation over data stream sliding windows. We show that a false-negative approach allowing a controlled number of frequent itemsets to be missing from the output is a more promising solution for mining frequent itemsets from a ubiquitous data stream. These are simple to implement, and have provable quality, space, and time guarantees. The experimental results have shown that the proposed algorithms achieve a high accuracy of at least 99% and require a small execution time.

• 出版日期2012-6