Mining the frequency of time-constrained serial episodes over massive data sequences and streams

摘要

With the popularity and development of the Internet, telecommunication, industrial systems etc., massive amounts of event sequences and streams have been and are being produced. These sequences and streams are generated at a fast pace posing grand challenges in computation and analysis. On one hand, due to the huge number of events, analyzing the sequences is time-consuming. On the other hand, as events in a stream may not necessarily arrive in uniform speed, an effective computational model over the stream should be able to accommodate the intensive arrival of events. In this work, we focus on frequency evaluation which is one representative task in sequence and stream analysis. To address the challenges listed above, we present a one-pass algorithm, namely ONCE, which outputs a popularly used frequency from a given sequence. Moreover, we also present a pair of advanced models, SparkONCE and StreamingONCE, respectively. Both of these approaches are built on ONCE. With a series of non-trivial strategies carefully designed towards Spark, SparkONCE and StreamingONCE exhibit superior performances with respect to ONCE. In particular, compared to ONCE, SparkONCE significantly improves the efficiency in massive sequences; StreamingONCE can effectively adapt to the uneven speed for the events in a stream. The experimental study on real-world and synthetic datasets demonstrate that the proposed approach can work well on massive sequences and streams.