A sliding window‐based false‐negative approach for ubiquitous data stream analysis
Young‐Hee Kim, Doo-Soon Park, Hee-Wan Kim, Ungmo Kim · International Journal of Communication Systems · 2011
SUMMARY 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. Copyright © 2011 John Wiley & Sons, Ltd.