Swarm
Authors:
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 723-734
Abstract
Recent improvements in positioning technology make massive moving object data widely available. One important analysis is to find the moving objects that travel together. Existing methods put a strong constraint in defining moving object cluster, that they require the moving objects to stick together for consecutive timestamps. Our key observation is that the moving objects in a cluster may actually diverge temporarily and congregate at certain timestamps. Motivated by this, we propose the concept of swarm which captures the moving objects that move within arbitrary shape of clusters for certain timestamps that are possibly non-consecutive. The goal of our paper is to find all discriminative swarms, namely closed swarm . While the search space for closed swarms is prohibitively huge, we design a method, ObjectGrowth, to efficiently retrieve the answer. In ObjectGrowth, two effective pruning strategies are proposed to greatly reduce the search space and a novel closure checking rule is developed to report closed swarms on-the-fly. Empirical studies on the real data as well as large synthetic data demonstrate the effectiveness and efficiency of our methods.Keywords
This publication has 19 references indexed in Scilit:
- Reporting flock patternsComputational Geometry, 2008
- Aerobic Oxidation of Alcohols with Carbon-Supported Pt CatalystSynfacts, 2008
- Discovery of convoys in trajectory databasesProceedings of the VLDB Endowment, 2008
- Efficient mining of group patterns from user movement dataData & Knowledge Engineering, 2006
- Constraints on SUSY lepton flavour violation by rare processesJournal of High Energy Physics, 2005
- On Discovering Moving Clusters in Spatio-temporal Data2005
- Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree ApproachData Mining and Knowledge Discovery, 2004
- CloSpan: Mining: Closed Sequential Patterns in Large Datasets2003
- Analyzing Relative Motion within Groups ofTrackable Moving Point Objects2002
- CHARM: An Efficient Algorithm for Closed Itemset Mining2002