research-article

On Discovery of Spatiotemporal Influence-Based Moving Clusters

Author:

Dhaval PatelAuthors Info & Claims

ACM Transactions on Intelligent Systems and Technology (TIST), Volume 6, Issue 1

Article No.: 4, Pages 1 - 23

https://doi.org/10.1145/2631926

Published: 11 March 2015 Publication History

Abstract

A moving object cluster is a set of objects that move close to each other for a long time interval. Existing works have utilized object trajectories to discover moving object clusters efficiently. In this article, we define a spatiotemporal influence-based moving cluster that captures spatiotemporal influence spread over a set of spatial objects. A spatiotemporal influence-based moving cluster is a sequence of spatial clusters, where each cluster is a set of nearby objects, such that each object in a cluster influences at least one object in the next immediate cluster and is also influenced by an object from the immediate preceding cluster. Real-life examples of spatiotemporal influence-based moving clusters include diffusion of infectious diseases and spread of innovative ideas. We study the discovery of spatiotemporal influence-based moving clusters in a database of spatiotemporal events. While the search space for discovering all spatiotemporal influence-based moving clusters is prohibitively huge, we design a method, STIMer, to efficiently retrieve the maximal answer. The algorithm STIMer adopts a top-down recursive refinement method to generate the maximal spatiotemporal influence-based moving clusters directly. Empirical studies on the real data as well as large synthetic data demonstrate the effectiveness and efficiency of our method.

References

[1]

D. Agarwal, A. McGregor, J. Phillips, S. Venky, and Z. Zhu. 2006. Spatial scan statistics: Approximations and performance study. In SIGKDD. 24--33.

Digital Library

[2]

H. Aung and K. Tan. 2012. Mining multi-object spatial-temporal movement patterns. SIGSPATIAL Special 4, 3 (Nov. 2012), 14--19.

Digital Library

[3]

D. Birant and A. Kut. 2007. ST-DBSCAN: An algorithm for clustering spatial-temporal data. Data Knowl. Eng. 60, 1 (2007), 208--221.

Digital Library

[4]

X. Caon, G. Cong, and C. Jensen. 2010. Mining significant semantic locations from GPS data. In VLDB. 320--332.

[5]

M. Celik, S. Shekar, J. Rogers, J. Shine, and J. Kang. 2008. Mining at most top-k mixed-drove spatio-temporal co-occurrence patterns: A summary of results. In SSTD. 187--192.

[6]

W. Chang, D. Zeng, and H. Chen. 2008. A spatio-temporal data analysis approach based on prospective support vector clustering. Decision Support Systems (2008).

[7]

W. Dong, X. Zhang, L. Li, C. Sun, L. Shi, and S. Wei. 2012. Detecting irregularly shaped significant spatial and spatio-temporal clusters. SDM. 732--743.

[8]

M. Ester, H. Kriegel, J. Sander, and X. Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD. 226--231.

[9]

S. Gaffney and P. Smyth. 1999. Trajectory clustering with mixtures of regression models. In KDD. 63--72.

Digital Library

[10]

H. Gonzalez, J. Han, and X. Li. 2006. Mining compressed commodity workflows from massive RFID data sets. In IKM. 162--171.

Digital Library

[11]

J. Gudmundsson, M. van Kreveld, and B. Speckmann. 2004. Efficient detection of motion patterns in spatio-temporal data sets. In GIS. 20--25.

Digital Library

[12]

D. Guo, S. Liua, and H. Jina. 2010. A graph-based approach to vehicle trajectory analysis. In JLBS, 4. 183--199.

Digital Library

[13]

Y. Huang, L. Zhang, and P. Zhang. 2008. A framework for mining sequential patterns from spatio-temporal event data set. In TKDE. 433--448.

Digital Library

[14]

H. Jeung, M. Yiu, X. Zhou, C. Jensen, and H. Shen. 2008. Discovery of convoys in trajectory databases. In PVLDB. 1068--1080.

Digital Library

[15]

P. Kalnis, N. Mamoulis, and S. Bakiras. 2005. On discovering moving clusters in spatio-temporal data. In SSTD. 364--381.

Digital Library

[16]

M. Kreveld and J. Luo. 2007. The definition and computation of trajectory and subtrajectory similarity. In GIS. 1--4.

Digital Library

[17]

H.-P. Kriegel and M. Pfeifle. 2005. Clustering moving objects via medoid clusterings. In SSDBM. 153--162.

Digital Library

[18]

M. Kulldorff, W. Athas, E. Feuer, B. Miller, and C. Key. 1998. Evaluating cluster alarms: A space-time scan statistic and brain cancer in Los Alamos. In AJPH. 1377--1380.

[19]

J.-G. Lee, J. Han, and X. Li. 2008. Trajectory outlier detection: A partition-and-detect framework. In ICDE (2008), 140--149.

Digital Library

[20]

J.-G. Lee, J. Han, and K.-Y. Whang. 2007. Trajectory clustering: A partition-and-group framework. In SIGMOD. 10--22.

Digital Library

[21]

N. Levine. 2010. CrimeStat: A Spatial Statistics Program for the Analysis of Crime Incident Locations (v 3.3). Ned Levine and Associates, Houston, TX, and the National Institute of Justice, Washington, DC.

[22]

Y. Li, J. Han, and J. Yang. 2004. Clustering moving objects. In KDD. 617--622.

Digital Library

[23]

Z. Li, B. Ding, J. Han, and R. Kays. 2010. Swarm: Mining relaxed temporal moving object clusters. VLDB Endow. 3, 1--2 (2010), 723--734.

Digital Library

[24]

R. Maciejewski, R. Hafen, S. Rudolph, S. Larew, M. W. Cleveland, and D. Ebert. 2011. Forecasting hotspots: A predictive analytics approach. IEEE Trans. Visual. Comput. Graphics 17, 4 (2011), 440--453.

Digital Library

[25]

S. Mohammadi, V. Janeja, and A. Gangopadhyay. 2009. Discretized spatio-temporal scan window. In SIAM. 1195--1206.

[26]

P. Mohan, S. Shekhar, J. Shine, and J. Rogers. 2010. Cascading spatio-temporal pattern discovery: A summary of results. In SDM. 327--338.

[27]

A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti. 2009. WhereNext: A location predictor on trajectory pattern mining. In KDD. 10--20.

Digital Library

[28]

D. Neill, A. Moore, M. Sabhnani, and K. Daniel. 2005. Detection of emerging space-time clusters. In ACM SIGKDD. 218--227.

Digital Library

[29]

D. Patel, C. Sheng, W. Hsu, and M. Lee. 2012. Incorporating duration information for trajectory classification. In ICDE. 1132--1143.

Digital Library

[30]

T. Sakaki, M. Okazaki, and Y. Matsuo. 2008. Earthquake shakes twitter users: Real-time event detection by social sensors. In WWW. 697--713.

Digital Library

[31]

S. Shekhar and Y. Huang. 2001. Discovering spatial co-location patterns: A summary of results. In SSTD. 236--256.

Digital Library

[32]

M. Spiliopoulou, I. Ntoutsi, Y. Theodoridis, and R. Schult. 2006. MONIC: Modeling and monitoring cluster transitions. In KDD. 706--711.

Digital Library

[33]

L. Tang, Y. Zheng, J. Yuan, J. Han, A. Leung, W. Peng, and T. Porta. 2014. A framework of traveling companion discovery on trajectory data streams. ACM Trans. Intell. Syst. Technol. 5, 1 (Jan. 2014), 3:1--3:34.

Digital Library

[34]

M. Vieira, P. Bakalov, V. Tsotras, and J. Vassilis. 2009. On-line discovery of flock patterns in spatio-temporal data. In GIS. 286--295.

Digital Library

[35]

J. Wang, W. Hsu, M. L. Lee, and J. Wang. 2004. FlowMiner: Finding flow patterns in spatio-temporal databases. In ICTAI. 14--21.

Digital Library

[36]

R. Watkins, S. Eagleson, S. Beckett, G. Garner, B. Veenendaal, G. Wright, and A. Plant. 2007. Using GIS to create synthetic disease outbreaks. In BMC Medical Informatics and Decision Making.

[37]

L. Wie and M. Shan. 2006. Efficient mining of spatial co-orientation patterns from image databases. In SMC. 2982--2987.

[38]

D. Zeng, H. Chen, C. Chavez, W. Lober, and M. Thurmond. 2010. Infectious Disease Informatics and Biosurveillance. Springer (2010).

Digital Library

[39]

M. Zhang, W. Hsu, and M. L. Lee. 2007. Finding orientation-sensitive patterns in snapshot databases. In ICTAI. IEEE, 171--178.

Digital Library

Cited By

Zhang PMiao LWang FLi X(2023)Discovering Geographical Flock Patterns of CO2 Emissions in China Using Trajectory Mining TechniquesInternational Journal of Environmental Research and Public Health10.3390/ijerph2005426520:5(4265)Online publication date: 27-Feb-2023
https://doi.org/10.3390/ijerph20054265
Hu CChen S(2021)Massively Parallel Discovery of Loosely Moving Congestion Patterns from Trajectory DataISPRS International Journal of Geo-Information10.3390/ijgi1011078710:11(787)Online publication date: 17-Nov-2021
https://doi.org/10.3390/ijgi10110787
Xie LTao DWei H(2016)Joint Structured Sparsity Regularized Multiview Dimension Reduction for Video-Based Facial Expression RecognitionACM Transactions on Intelligent Systems and Technology10.1145/29565568:2(1-21)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2956556
Show More Cited By

Index Terms

On Discovery of Spatiotemporal Influence-Based Moving Clusters
1. Information systems
  1. Information systems applications

Recommendations

Discovering Moving Clusters from Spatial-Temporal Databases
ISDA '08: Proceedings of the 2008 Eighth International Conference on Intelligent Systems Design and Applications - Volume 01

Owing to the advances of computer and communication technologies, clustering analysis on moving objects has attracted increasing attention in recent years. An interesting pattern is to find the moving clusters that are composed of objects moving along ...
Comparing clustering algorithms and their influence on the evolution of labeled clusters
DEXA'07: Proceedings of the 18th international conference on Database and Expert Systems Applications

We study the influence of different clustering algorithms on cluster evolution monitoring in data streams. The capturing and interpretation of cluster change delivers indicators on the evolution of the underlying population. For text stream monitoring, ...
A new validity index for crisp clusters

In this paper, a new cluster validity index which can be considered as a measure of the accuracy of the partitioning of data sets is proposed. The new index, called the STR index, is defined as the product of two components which determine changes of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Intelligent Systems and Technology

ACM Transactions on Intelligent Systems and Technology Volume 6, Issue 1

April 2015

255 pages

ISSN:2157-6904

EISSN:2157-6912

DOI:10.1145/2745393

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2015

Accepted: 01 June 2014

Revised: 01 June 2014

Received: 01 April 2013

Published in TIST Volume 6, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
310
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang PMiao LWang FLi X(2023)Discovering Geographical Flock Patterns of CO2 Emissions in China Using Trajectory Mining TechniquesInternational Journal of Environmental Research and Public Health10.3390/ijerph2005426520:5(4265)Online publication date: 27-Feb-2023
https://doi.org/10.3390/ijerph20054265
Hu CChen S(2021)Massively Parallel Discovery of Loosely Moving Congestion Patterns from Trajectory DataISPRS International Journal of Geo-Information10.3390/ijgi1011078710:11(787)Online publication date: 17-Nov-2021
https://doi.org/10.3390/ijgi10110787
Xie LTao DWei H(2016)Joint Structured Sparsity Regularized Multiview Dimension Reduction for Video-Based Facial Expression RecognitionACM Transactions on Intelligent Systems and Technology10.1145/29565568:2(1-21)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2956556
Lacerda TFernandes S(2016)Scalable Real-Time Flock Detection2016 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2016.7842241(1-7)Online publication date: Dec-2016
https://doi.org/10.1109/GLOCOM.2016.7842241

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents