Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Due to the advances in positioning technologies, the real time information of moving objects becomes increasingly available, which has posed new challenges to the database research. As a long-standing technique to identify overall distribution patterns in data, clustering has achieved brilliant successes in analyzing static datasets. In this paper, we study the problem of clustering moving objects, which could catch interesting pattern changes during the motion process and provide better insight into the essence of the mobile data points. In order to catch the spatial-temporal regularities of moving objects and handle large amounts of data, micro-clustering [20] is employed. Efficient techniques are proposed to keep the moving micro-clusters geographically small. Important events such as the collisions among moving micro-clusters are also identified. In this way, high quality moving micro-clusters are dynamically maintained, which leads to fast and competitive clustering result at any given time instance. We validate our approaches with a through experimental evaluation, where orders of magnitude improvement on running time is observed over normal K-Means clustering method [14].

REFERENCES

• 1: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, ACM SIGMOD Record, v.28 n.2, p.49-60, June 1999
• 2: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, ACM SIGMOD Record, v.27 n.2, p.94-105, June 1998
• 3: Julien Basch , Leonidas J. Guibas, Data structures for mobile data, Journal of Algorithms, v.31 n.1, p.1-28, April 1999 [doi>10.1006/jagm.1998.0988]
• 4: Julien Basch , Leonidas J. Guibas , G. D. Ramkumar, Sweeping lines and line segments with a heap, Proceedings of the thirteenth annual symposium on Computational geometry, p.469-471, June 04-06, 1997, Nice, France [doi>10.1145/262839.263089]
• 5: Darya Chudova , Scott Gaffney , Eric Mjolsness , Padhraic Smyth, Translation-invariant mixture models for curve clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956763]
• 6: Guilherme D. da Fonseca , Celina M. H. de Figueiredo, Kinetic heap-ordered trees: tight analysis and improved algorithms, Information Processing Letters, v.85 n.3, p.165-169, 14 February 2003 [doi>10.1016/S0020-0190(02)00366-6]
• 7: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 8: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 9: S. Har-Peled, Clustering Motion, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.84, October 14-17, 2001
• 10: G. S. Iwerks, H. Samet, and K. Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. VLDB, 2003.
• 11: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 12: George Karypis , Eui-Hong (Sam) Han , Vipin Kumar, Chameleon: Hierarchical Clustering Using Dynamic Modeling, Computer, v.32 n.8, p.68-75, August 1999 [doi>10.1109/2.781637]
• 13: Library for Efficient Data types and Algorithms. <http://www.algorithmic-solutions.com/enleda.htm>.
• 14: J. MacQueen. Some methods for classification and analysis of multivariate observations. Proc. 5th Berkeley Symp. Math. Statist, 1967.
• 15: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 16: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 17: Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564730]
• 18: Wei Wang , Jiong Yang , Richard R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, Proceedings of the 23rd International Conference on Very Large Data Bases, p.186-195, August 25-29, 1997
• 19: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]
• 20: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
algorithms, clustering, micro-cluster, moving object