Zhenhui Li
Jiawei Han
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.
- R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In VLDB, 1994. Google Scholar
Digital Library
- G. Al-Naymat, S. Chawla, and J. Gudmundsson. Dimensionality reduction for long duration and complex spatio-temporal queries. In SAC, 2007. Google ScholarDigital Library
- I. Assent, R. Krieger, E. Müller, and T. Seidl. Inscy: Indexing subspace clusters with in-process-removal of redundancy. In ICDM, 2008. Google ScholarDigital Library
- M. Benkert, J. Gudmundsson, F. Hubner, and T. Wolle. Reporting flock patterns. In COMGEO, 2008.Google ScholarDigital Library
- L. Chen and R. T. Ng. On the marriage of lp-norms and edit distance. In VLDB, 2004. Google ScholarDigital Library
- L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. In SIGMOD, 2005. Google ScholarDigital Library
- M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases. In KDD, 1996.Google Scholar
- S. Gaffney, A. Robertson, P. Smyth, S. Camargo, and M. Ghil. Probabilistic clustering of extratropical cyclones using regression mixture models. In Technical Report UCI-ICS 06-02, 2006.Google Scholar
- J. Gudmundsson and M. van Kreveld. Computing longest duration flocks in trajectory data. In GIS, 2006. Google ScholarDigital Library
- J. Gudmundsson, M. J. van Kreveld, and B. Speckmann. Efficient detection of motion patterns in spatio-temporal data sets. In GIS, 2004. Google ScholarDigital Library
- J. Han, J. Pei, Y. Yin, and R. Mao. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. DMKD, 2004. Google ScholarDigital Library
- H. Jeung, H. T. Shen, and X. Zhou. Convoy queries in spatio-temporal databases. In ICDE, 2008. Google ScholarDigital Library
- H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen. Discovery of convoys in trajectory databases. In PVLDB, 2008. Google ScholarDigital Library
- P. Kalnis, N. Mamoulis, and S. Bakiras. On discovering moving clusters in spatio-temporal data. In SSTD, 2005. Google ScholarDigital Library
- P. Kröger, H.-P. Kriegel, and K. Kailing. Density-connected subspace clustering for high-dimensional data. In SDM, 2004.Google Scholar
- P. Laube and S. Imfeld. Analyzing relative motion within groups of trackable moving point objects. In GIS, 2002. Google ScholarDigital Library
- J.-G. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: A partition-and-group framework. In SIGMOD, 2007. Google ScholarDigital Library
- Z. Li, M. Ji, J.-G. Lee, L. Tang, Y. Yu, J. Han, and R. Kays. Movemine: Mining moving object databases, to appear. In SIGMOD, 2010. Google ScholarDigital Library
- J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In DMKD, 2000.Google Scholar
- M. Vlachos, D. Gunopulos, and G. Kollios. Discovering similar multidimensional trajectories. In ICDE, 2002. Google ScholarDigital Library
- J. Wang, J. Han, and J. Pei. Closet+: searching for the best strategies for mining frequent closed itemsets. In KDD, 2003. Google ScholarDigital Library
- Y. Wang, E.-P. Lim, and S.-Y. Hwang. Efficient mining of group patterns from user movement data. In DKE, 2006. Google ScholarDigital Library
- X. Yan, J. Han, and R. Afshar. CloSpan: Mining closed sequential patterns in large datasets. In SDM, 2003.Google ScholarCross Ref
- B.-K. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In ICDE, 1998. Google ScholarDigital Library
- M. J. Zaki and C. J. Hsiao. Charm: An efficient algorithm for closed itemset mining. In SDM, 2002.Google ScholarCross Ref
Index Terms
- Swarm: mining relaxed temporal moving object clusters
Recommendations
Euclidean Particle Swarm Optimization
ICINIS '09: Proceedings of the 2009 Second International Conference on Intelligent Networks and Intelligent SystemsParticle swarm optimization (PSO) is a swarm intelligence algorithm, has been successfully applied to many engineering optimization problems and shown its high search speed in these applications. However, as the dimension and the number of local optima ...
Dynamic multi-swarm particle swarm optimizer with harmony search
In this paper, the dynamic multi-swarm particle swarm optimizer (DMS-PSO) is improved by hybridizing it with the harmony search (HS) algorithm and the resulting algorithm is abbreviated as DMS-PSO-HS. We present a novel approach to merge the HS ...
Enhanced particle swarm optimization with multi-swarm and multi-velocity for optimizing high-dimensional problems
Traditional particle swarm optimization (PSO) algorithm mainly relies on the history optimal information to guide its optimization. However, when the traditional PSO algorithm searches high-dimensional complex problems, wrong position information of the ...
Comments