Paper Info
Title
An index-based method for timestamped event sequence matching
Abstract
This paper addresses the problem of timestamped event sequence matching, a new type of sequence matching that retrieves the occurrences of interesting patterns from a timestamped event sequence. Timestamped event sequence matching is useful for discovering temporal causal relationships among timestamped events. In this paper, we first point out the shortcomings of prior approaches to this problem and then propose a novel method that employs an R∗-tree to overcome them. To build an R∗-tree, it places a time window at every position of a timestamped event sequence and represents each window as an n-dimensional rectangle by considering the first and last occurrence times of each event type. Here, n is the total number of disparate event types that may occur in a target application. When n is large, we apply a grouping technique to reduce the dimensionality of an R∗-tree. To retrieve the occurrences of a query pattern from a timestamped event sequence, the proposed method first identifies a small number of candidates by searching an R∗-tree and then picks out true answers from them. We prove its robustness formally, and also show its effectiveness via extensive experiments.
Year
DOI
Venue
2005
10.1007/11546924_48
DEXA
Keywords
Field
DocType
novel method,event type,new type,sequence matching,timestamped event,timestamped event sequence,timestamped event sequence matching,small number,disparate event type,index-based method,indexation,similarity search
Small number,Data mining,R-tree,Computer science,Rectangle,Search engine indexing,Curse of dimensionality,Robustness (computer science),Reactive system,Database,Nearest neighbor search
Conference
Volume
ISSN
ISBN
3588
0302-9743
3-540-28566-0
Citations 
PageRank 
References 
0
0.34
13
Authors
4
Name
Order
Citations
PageRank
Sanghyun Park172980.64
Jung-Im Won28610.56
Jee-Hee Yoon3498.70
Sang-Wook Kim4792152.77