On finding frequent patterns in event sequences

Andrea Campagna; Rasmus Pagh

On finding frequent patterns in event sequences

Andrea Campagna, Rasmus Pagh

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

Given a directed acyclic graph with labeled vertices, we consider the problem of finding the most common label sequences (``traces'') among all paths in the graph (of some maximum length $m$). Since the number of paths can be huge, we propose novel algorithms whose time complexity depends only on the size of the graph, and on the frequency $\varepsilon$ of the most frequent traces. In addition, we apply techniques from streaming algorithms to achieve space usage that depends only on $\varepsilon$, and not on the number of distinct traces.

The abstract problem considered models a variety of tasks concerning finding frequent patterns in event sequences. Our motivation comes from working with a data set of 2 million RFID readings from baggage trolleys at Copenhagen Airport. The question of finding frequent passenger movement patterns is mapped to the above problem. We report on experimental findings for this data set.

Original language	English
Title of host publication	ICDM 2010 : Proceedings of the Tenth IEEE International Conference on Data Mining
Number of pages	6
Publisher	IEEE
Publication date	14 Dec 2010
Publication status	Published - 14 Dec 2010
Event	IEEE Internation conference on data mining - Sydney, Australia Duration: 14 Dec 2010 → 17 Dec 2010 http://www.cs.uvm.edu/~icdm/

Conference

Conference	IEEE Internation conference on data mining
Country/Territory	Australia
City	Sydney
Period	14/12/2010 → 17/12/2010
Internet address	http://www.cs.uvm.edu/~icdm/

Keywords

Directed acyclic graph
Frequent pattern mining
Trace analysis
Streaming algorithms
Event sequences

Cite this

@inproceedings{4e47857dacb14f38911c87de799be149,

title = "On finding frequent patterns in event sequences",

abstract = "Given a directed acyclic graph with labeled vertices, we consider the problem of finding the most common label sequences (``traces'') among all paths in the graph (of some maximum length $m$). Since the number of paths can be huge, we propose novel algorithms whose time complexity depends only on the size of the graph, and on the frequency $\varepsilon$ of the most frequent traces. In addition, we apply techniques from streaming algorithms to achieve space usage that depends only on $\varepsilon$, and not on the number of distinct traces.The abstract problem considered models a variety of tasks concerning finding frequent patterns in event sequences. Our motivation comes from working with a data set of 2 million RFID readings from baggage trolleys at Copenhagen Airport. The question of finding frequent passenger movement patterns is mapped to the above problem. We report on experimental findings for this data set.",

keywords = "Directed acyclic graph, Frequent pattern mining, Trace analysis, Streaming algorithms, Event sequences, Directed acyclic graph, Frequent pattern mining, Trace analysis, Streaming algorithms, Event sequences",

author = "Andrea Campagna and Rasmus Pagh",

year = "2010",

month = dec,

day = "14",

language = "English",

booktitle = "ICDM 2010",

publisher = "IEEE",

address = "United States",

note = "IEEE Internation conference on data mining, ICDM 2010 ; Conference date: 14-12-2010 Through 17-12-2010",

url = "http://www.cs.uvm.edu/~icdm/",

}

TY - GEN

T1 - On finding frequent patterns in event sequences

AU - Campagna, Andrea

AU - Pagh, Rasmus

PY - 2010/12/14

Y1 - 2010/12/14

N2 - Given a directed acyclic graph with labeled vertices, we consider the problem of finding the most common label sequences (``traces'') among all paths in the graph (of some maximum length $m$). Since the number of paths can be huge, we propose novel algorithms whose time complexity depends only on the size of the graph, and on the frequency $\varepsilon$ of the most frequent traces. In addition, we apply techniques from streaming algorithms to achieve space usage that depends only on $\varepsilon$, and not on the number of distinct traces.The abstract problem considered models a variety of tasks concerning finding frequent patterns in event sequences. Our motivation comes from working with a data set of 2 million RFID readings from baggage trolleys at Copenhagen Airport. The question of finding frequent passenger movement patterns is mapped to the above problem. We report on experimental findings for this data set.

AB - Given a directed acyclic graph with labeled vertices, we consider the problem of finding the most common label sequences (``traces'') among all paths in the graph (of some maximum length $m$). Since the number of paths can be huge, we propose novel algorithms whose time complexity depends only on the size of the graph, and on the frequency $\varepsilon$ of the most frequent traces. In addition, we apply techniques from streaming algorithms to achieve space usage that depends only on $\varepsilon$, and not on the number of distinct traces.The abstract problem considered models a variety of tasks concerning finding frequent patterns in event sequences. Our motivation comes from working with a data set of 2 million RFID readings from baggage trolleys at Copenhagen Airport. The question of finding frequent passenger movement patterns is mapped to the above problem. We report on experimental findings for this data set.

KW - Directed acyclic graph

KW - Frequent pattern mining

KW - Trace analysis

KW - Streaming algorithms

KW - Event sequences

KW - Directed acyclic graph

KW - Frequent pattern mining

KW - Trace analysis

KW - Streaming algorithms

KW - Event sequences

M3 - Article in proceedings

BT - ICDM 2010

PB - IEEE

T2 - IEEE Internation conference on data mining

Y2 - 14 December 2010 through 17 December 2010

ER -

On finding frequent patterns in event sequences

Abstract

Conference

Keywords

Fingerprint

Cite this