Zips : mining compressing sequential patterns in streams

T.L. Hoang, T.G.K. Calders, J. Yang, F. Mörchen, D. Fradkin

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
2 Downloads (Pure)

Abstract

We propose a streaming algorithm, based on the minimal description length (MDL) principle, for extracting non-redundant sequential patterns. For static databases, the MDL-based approach that selects patterns based on their capacity to compress data rather than their frequency, was shown to be remarkably effective for extracting meaningful patterns and solving the redundancy issue in frequent itemset and sequence mining. The existing MDL-based algorithms, however, either start from a seed set of frequent patterns, or require multiple passes through the data. As such, the existing approaches scale poorly and are unsuitable for large datasets. Therefore, our main contribution is the proposal of a new, streaming algorithm, called Zips, that does not require a seed set of patterns and requires only one scan over the data. For Zips, we extended the Lempel-Ziv (LZ) compression algorithm in three ways: first, whereas LZ assigns codes uniformly as it builds up its dictionary while scanning the input, Zips assigns codewords according to the usage of the dictionary words; more heaviliy used words get shorter code-lengths. Secondly, Zips exploits also non-consecutive occurences of dictionary words for compression. And, third, the well-known space-saving algorithm is used to evict unpromising words from the dictionary. Experiments on one synthetic and two real-world large-scale datasets show that our approach extracts meaningful compressing patterns with similar quality to the state-of-the-art multi-pass algorithms proposed for static databases of sequences. Moreover, our approach scales linearly with the size of data streams while all the existing algorithms do not.
Original languageEnglish
Title of host publicationProceedings of the ACM SIGKDD Workshop on Interactive Data Exploration and Analytics (IDEA'13, Chicago IL, USA, August 11-14, 2013)
EditorsD.H. Chau, J. Vreeken, M. Leeuwen, van, C. Faloutsos
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages54-62
ISBN (Print)978-1-4503-2329-1
DOIs
Publication statusPublished - 2013
Eventconference; ACM SIGKDD Workshop on Interactive Data Exploration and Analytics (IDEA'13); 2013-08-11; 2013-08-11 -
Duration: 11 Aug 201311 Aug 2013

Conference

Conferenceconference; ACM SIGKDD Workshop on Interactive Data Exploration and Analytics (IDEA'13); 2013-08-11; 2013-08-11
Period11/08/1311/08/13
OtherACM SIGKDD Workshop on Interactive Data Exploration and Analytics (IDEA'13)

Fingerprint Dive into the research topics of 'Zips : mining compressing sequential patterns in streams'. Together they form a unique fingerprint.

Cite this