We present an online method for frequent episode mining of streaming data. Although the extraction of frequent patterns has been actively studied in the field of episode mining, an optimal method suitable for streaming data has yet to be determined. In this study, we decompose an arbitrary sequence into a set of simple pre- and post-event relations called root-orders. This decomposition facilitates utilizing arbitrary, efficient methods for closed itemset mining in the online setting. Consequently, the proposed method is the first and most complete algorithm for extracting the so-called closed sequences with distance. We empirically verified the availability of the extracted output in a sequence prediction problem. We also investigated its ability to recover the original solution derived using existing methods for episode mining.

In recent years, there arises a new opportunity for discovering transient phenomena such as supernovae, solar flares, and bursty events from detecting unknown transient patterns in astronomical time-series data. However, since these transient phenomena usually happen with unpredictable characteristics in shapes, sizes, and durations, scientists might lose some significant information due to the huge volume of astronomical data to be analyzed. Data sketching is useful to deal with such huge time-series data. A simple sketching technique is known as binning that captures the statistical summary of each bin of data points. In this paper, we attempt to provide a novel framework of data sketching for a statistical hypothesis testing and apply it for unknown transient pattern detection. The principal idea of statistical hypothesis testing lies in that two short-term and similar bins are mergeable into a long-term bin. By applying our proposed method, we suppress the unnecessary data while keeping the primary information without setting the bin size in advance. We evaluate our proposed method through experiments on the light curves in real-world data from telescopes with synthetic mixed-type transient patterns. Experimental results demonstrate that our proposed method outperforms several frameworks of transient pattern detection in astronomy.

Essentially, any negative association rules are constructed over infrequent underling itemsets, thus the number of valid negative rules is always quite huge, and effective extraction of negative rules is quite difficult. In this paper, we study an efficient mining algorithm of negative rules over minimal generators, where a set of negative rules can be effectively compressed by using minimal generators, especially for dense data. We first propose new two concepts, so called consistency and non-redundancy, for a set consisting of both positive and negative association rules. Next, we prove some a fundamental but important property for minimal generators, which enables us to construct a suffix tree over minimal generators. We show a new top-down algorithm for mining a consistent and non-redundant set of negative association rules. The top-down search uses the suffix tree in order to restrict some negative rules to be right-minimal, which also suppress the burst of negative rules. Finally, we show preliminary results of experimental evaluation for the proposed negative rule mining method.

Abstract Here, we present a novel algorithm for frequent itemset mining in streaming data (FIM-SD). For the past decade, various FIM-SD methods in one-pass approximation settings that allow to approximate the support of each itemset have been proposed. They can be categorized into two approximation types: parameter-constrained (PC) mining and resource-constrained (RC) mining. PC methods control the maximum error that can be included in the approximate support based on a pre-defined parameter. In contrast, RC methods limit the maximum memory consumption based on resource constraints. However, the existing PC methods can exponentially increase the memory consumption, while the existing RC methods can rapidly increase the maximum error. In this study, we address this problem by introducing a hybrid approach of PC-RC approximations, called PARASOL. For any streaming data, PARASOL ensures to provide a condensed representation, called a Δ-covered set, which is regarded as an extension of the closedness compression; when Δ = 0, the solution corresponds to the ordinary closed itemsets. PARASOL searches for such approximate closed itemsets that can restore the frequent itemsets and their supports while the maximum error is bounded by an integer, Δ. Then, we empirically demonstrate that the proposed algorithm significantly outperforms the state-of-the-art PC and RC methods for FIM-SD.

In this paper, we study acceleration methods for on-line stream mining of all frequent closed itemsets under a minimal-size restriction. The algorithm LC-K-CloStream [3] can perform an 6-approximation on-line mining based on incremental intersection of transactions. We first integrate LC-K-CloStream with an extended FP-tree with skipping in order to effectively compress a huge number of mined closed itemsets. Next, we introduce novel pruning methods for rejecting a hopeless intersection computation by using look-ahead maximal-size estimation. We show, through experimental evaluations, that the proposed methods have a great performance for mining a large set of closed itemsets in dense data sets.

We propose a new on-line e-approximation algorithm for mining closed itemsets from a transactional data stream, which is also based on the incremental/cumulative intersection principle. The proposed algorithm, called LC-CloStream, is constructed by integrating CloStream algorithm and Lossy Counting algorithm. We investigate some behaviors of the LC-CloStream algorithm. Firstly we show the incompleteness and the semi-completeness for mining all frequent closed itemsets in a stream. Next, we give the completeness of eapproximation for extracting frequent itemsets.

This paper studies one-scan approximation algorithms for streaming data mining (SDM). Despite of the importance of pattern discovery in streaming data, this issue has not sufficiently addressed yet in the big data community. In this context, we briefly review the previously proposed SDM methods. There is a recent work to improve their limitation using the tecnique of online compression. It is based on the notion of Δ-cover. We then introduce them and show the experimental results obtained from high dimensional streaming transactions, each of which consists of about 10 thousand items. Consequently, the results demonstrate that we can drastically improve the scalability of SDM on the dimension number.

This study considers approximation techniques for frequent itemset mining from data streams (FIM-DS) under resource constraints. In FIM-DS, a challenging problem is handling a huge combinatorial number of entries (i.e., itemsets) to be generated from each streaming transaction and stored in memory. Various types of approximation methods have been proposed for FIM-DS. However, these methods require almost O(2L) space for the maximal length L of transactions. If some transaction contains sudden and intensive bursty events for a short span, they cannot work since memory consumption exponentially increases as L becomes larger. Thus, we present resource-oriented approximation algorithms that fix an upper bound for memory consumption to tolerate bursty transactions. The proposed algorithm requires only O(k) space for a resource-specified constant k and processes every transaction in O(kL) time. Consequently, the proposed algorithm can treat any transaction without memory overflow nor fatal response delay, while the output can be guaranteed to be no false negative under some conditions. Moreover, any (even if false negative) output is bounded within the approximation error which is dynamically determined in a resource-oriented manner. From an empirical viewpoint, it is necessary to maintain the error as low as possible. We tackle this problem by dynamically reducing the original stream. Through experimental results, we show that the resource-oriented approach can break the space limitation of previously proposed FIM-DS methods.