Mining Interesting Ratio Patterns over a Stream Sliding Window

In this paper, we aim to capture dependency among high correlated attributes in a sliding window of data streams at any time. Naive solutions cannot address combinatorial explosion problems. In order to generate highly correlated sets, we propose a candidate-generation rule based on Jaccard distance, and a generation method based on min-hashing functions to estimate the Jaccard distance without requiring to count supports explicitly. For mining frequent ratios, we introduce a concept of ratio range to reduce the candidate ratio sets efficiently. Additionally, the downward closure property of ratio patterns is also available to prune candidate sets. Our extensive experiments on both real and synthetic datasets verify the efficiency of our algorithms.