Mining Sequential Patterns using Two-Tail Time Effect

Author Name(s): *Gurram Sunitha
Author Email: gurramsunitha@gmail.com

Abstract

The temporal component of the spatio-temporal databases is the key factor that leads to large accumulation of data. It can be said that continuous collection of spatial data, leads to spatio-temporal databases. An event type sequence is called as a sequential pattern and extracting such sequential patterns from spatio-temporal event data sets paves way to define causal relationships between event types. In this paper, Relative Sequential Patterns (ReSPs) are introduced and an algorithm ReSP-Miner has been proposed to support efficient mining of the same. The interestingness measures proposed includes spatio-temporal features to be suitable for extraction of patterns from spatio-temporal databases. The proposed algorithm is evaluated in comparison with the STS-Miner algorithm for efficiency.

Keywords

Frequent Pattern Mining, Sequential Patterns, Spatio Temporal Databases, Events, Two-tail time effect.

Introduction

An event is the real-world object which inherently has spatial and temporal extent. Along with the object, if its location and time of occurrence are also recorded, the database is called as a spatio-temporal database. Hence, a spatio-temporal database contains both spatio-temporal as well as non-spatio-temporal attributes. Spatio-temporal extent of the data provides dynamic view of the underlying phenomenon. Algorithms handling extraction of sequential patterns from spatio-temporal databases has to mainly concentrate on: (1) scalability of algorithms as spatio-temporal databases are inherently large (2) design of efficient data structures to store and retrieve data quickly (3) design of good interestingness measures to prove the importance of sequential patterns.

Consider spatio-temporal database STDB, which consists of a set of events of various event types. The term event type is used to represent a type of event and the term event to represent the physical occurrence of an event type in the real-world. In some literature, events and event types are termed as ‘data observations’ and ‘data events’ respectively.  Each event defines a real-world event that has occurred at a definite location and time. Each event in the database is uniquely identified by its event ID and is described by its event type, location of occurrence, time of occurrence and context-level attributes. Each event belongs to any one of the event types. Let all the event types in the given spatio-temporal database be E = {E1, E2, …., En} where n specifies the number of event types. A relative sequential pattern is an event type sequence of form Ei → Ej → …. → Ek  where Ei, Ej, …Ek  ∈ E.

Conclusion

An algorithm ReSP-Miner has been proposed to extract relative sequential patterns from spatio-temporal event datasets. Interestingness measures ‘relative significance index’ and ‘significance index’ have been proposed to efficiently discover significant causal sequential patterns. The experimental results have shown that when there is high number of blocking patterns in the spatio-temporal dataset, ReSP-Miner has reduced time complexity and that ReSP-Miner outperforms STS-Miner by an order of magnitude in time.

1,079 total views, no views today

Download PDF File

About the author: tej