Mining Sequential Patterns using Two-Tail Time Effect

Author Name:
Author Email:

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.

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.

 

A discrete view of spatio-temporal conceptual model is assumed. Each event is considered to be a point in the space-time plane under observation. In real-world, the location of occurrence of an event can be represented by using latitude, longitude and elevation. Hence, generally location attribute is 3-dimensional. But, in scenarios where events have occurred with elevation near to 0, elevation need not be specified. Hence, in practice, location of occurrence of an event is considered to be 2-dimensional. Time of occurrence of event is 1-dimensional attribute where date and time of occurrence of the event in the real-world is recorded.

 

The main problem approached in this paper is to extract all significant causal patterns from the given spatio-temporal event database. Two interestingness measures ‘relative significance index’ and ‘significance index’ are proposed for efficient identification of causal interactions between event types and for measuring the significance of the relative sequential patterns respectively.

 

Since the idea of sequential pattern mining is proposed in [1], there has been colossal research done in this area. Substantial number of algorithms has been proposed to work with a variety of spatio-temporal databases such as trajectory databases, geographical databases, scientific databases, web traffic databases etc [2].

 

Work in [3], [4] has concentrated on mining frequent trajectory patterns by extending sequential pattern mining paradigm. [5] have proposed their theories on finding evolution patterns in satellite image time series. The authors have proposed significant work on extracting significant sequential patterns from spatio-temporal event datasets [6]. Roddick et al. [7] presented a brief review on spatial, temporal and spatio-temporal data mining. The authors of [8] have focused on presenting a scientific and systematic of statistical foundations for spatio-temporal data.

 

Alatrista-Salas et al. [9] proposed two algorithms, an apriori based approach and pattern-growth based approach for extracting patterns from spatio-temporal datasets. The algorithms have been evaluated on two data sets – water pollution data of rivers in France, dengue epidemics data of New Caledonia. The approach of assigning priorities to elements of patterns allows extraction of patterns focused with regard to event types, time periods, length of patterns etc. The research work presented in [10] is the first in its content applying weighted pattern mining approach to extract sequential patterns from spatio-temporal databases.

 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.

    References

  • Agrawal R, and Srikant R, “Mining Sequential Patterns,” in Proc. 1995 Int’l Conf. on Data Eng. (ICDE ‘95), Mar 1995.
  • Cao, N. Mamoulis, and D.W. Cheung, “Mining Frequent Spatio-Temporal Sequential Patterns,” in Proc. Fifth IEEE Int’l Conf. Data Mining (ICDM ’05), 2005.
  • Fosca Giannotti, Mirco Nanni, Fabio Pinelli, Dino Pedreschi, “Trajectory pattern mining,” In KDD’ 07, ACM NY, USA, pp 330-339.
  • Anthony J.T. Lee, Yi-An Chen,  Weng-Chong Ip. Mining frequent trajectory patterns in spatial–temporal databases. An International Journal of Information Sciences, Vol: 179, No. 13, 2009.
  • Julea et al. Unsupervised spatiotemporal mining of satellite image time series using grouped frequent sequential patterns. IEEE Transactions on Geoscience and Remote Sensing, Vol: 49, No. 4, Apr. 2011.
  • Huang, L. Zhang, and P. Zhang, “A framework for mining sequential patterns from spatio-temporal event data sets,” IEEE Transactions Knowledge Data Engineering, Vol: 20, No. 4, pp. 433–448, 2008.
  • Roddick J.F., Spiliopoulou M. A bibliography of temporal, spatial and spatio-temporal data mining research. SIGKDD Explor. Vol: 1, pp. 34–38, 1999.
  • Shekhar S, Jiang Z, Ali RY, Eftelioglu E, Tang X, Gunturi V, Zhou X. Spatiotemporal data mining: A computational perspective. ISPRS International Journal of Geo-Information, Vol: 4, No. 4, pp. 2306-38, Oct. 2015.
  • Alatrista-Salas H, Bringay S, Flouvat F, Selmaoui-Folcher N, Teisseire M. Spatio-sequential patterns mining: Beyond the boundaries. Intelligent Data Analysis, Vol: 20, No. 2, pp. 293-316, Jan. 2016.
  • Sunitha G, Reddy AR, “WRSP-Miner Algorithm for Mining Weighted Sequential Patterns from Spatio-temporal Databases,” in Proceedings of the Second International Conference on Computer and Communication Technologies, Springer India, pp. 309-317, 2016.
  • Sunitha Gurram. Grade-based Spatio-Temporal Sequential Pattern Mining using Support and Event Index Measures. Indian Journal of Science and Technology, Vol: 10, No. 20, May 2017.
  • Hamdi SM, Aydin B, Angryk RA, “A Pattern Growth-Based Approach for Mining Spatiotemporal Co-occurrence Patterns,” in 16th International Conference on Data Mining Workshops (ICDMW), IEEE, pp. 1125-1132, Dec. 2016.
  • Ma J, Zeng D, Zhao H, Liu C. Cross-correlation measure for mining spatio-temporal patterns. Journal of Database Management (JDM), Vol: 24, No. 2, pp. 13-34, Apr. 2013.
  • Fabrègue, M., Braud, A., Bringay, S., Le Ber, F., and Teisseire, M. Including spatial relations and scales within sequential pattern extraction. In Discovery Science, Springer Berlin Heidelberg, pp. 209-223, 2012.
  • Shen, W., Wang, J., and Han J. Sequential Pattern Mining. Frequent Pattern Mining, Springer International Publishing, pp. 261-282, 2014.
  • Dasgupta D, Roy S, Singha S, and Chakraborty A. Survey and Analysis of Mining Requirements in Spatio-Temporal Database. Computer, Communication and Electrical Technology, CRC Press, pp. 91-95, 2017.
  • Xylogiannopoulos, Konstantinos F., Panagiotis Karampelas, and Reda Alhajj. Frequent and Non-frequent Sequential Itemsets Detection. From Social Data Mining and Analysis to Prediction and Community Detection, Springer International Publishing, pp. 211-238, 2017.

DOWNLOAD THE COMPLETE RESEARCH PAPER PDF

18 total views, 0 views today

About the author: tej