On-line discovery of hot motion paths

ABSTRACT

We consider an environment of numerous moving objects, equipped with location-sensing devices and capable of communicating with a central coordinator. In this setting, we investigate the problem of maintaining hot motion paths, i.e., routes frequently followed by multiple objects over the recent past. Motion paths approximate portions of objects' movement within a tolerance margin that depends on the uncertainty inherent in positional measurements. Discovery of hot motion paths is important to applications requiring classification/profiling based on monitored movement patterns, such as targeted advertising, resource allocation, etc. To achieve this goal, we delegate part of the path extraction process to objects, by assigning to them adaptive lightweight filters that dynamically suppress unnecessary location updates and, thus, help reducing the communication overhead. We demonstrate the benefits of our methods and their efficiency through extensive experiments on synthetic data sets.

REFERENCES

• 1: Aris Anagnostopoulos , Michail Vlachos , Marios Hadjieleftheriou , Eamonn Keogh , Philip S. Yu, Global distance-based segmentation of trajectories, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150411]
• 2: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 3: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: Y. Cai, K. A. Hua, and G. Cao. Processing range-monitoring queries on heterogeneous mobile objects. In International Conference on Mobile Data Management (MDM), pages 27--38, 2004.
• 5: Hu Cao , Ouri Wolfson , Goce Trajcevski, Spatio-temporal data reduction with deterministic error bounds, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.211-228, September 2006 [doi>10.1007/s00778-005-0163-7]
• 6: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 7: Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066161]
• 8: D. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a digitised line or its caricature. The Canadian Cartographer Journal, 10(2):112--122, 1973.
• 9: Scott Gaffney , Padhraic Smyth, Trajectory clustering with mixtures of regression models, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.63-72, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312198]
• 10: Bugra Gedik , Ling Liu, MobiEyes: A Distributed Location Monitoring Service Using Moving Location Queries, IEEE Transactions on Mobile Computing, v.5 n.10, p.1384-1402, October 2006 [doi>10.1109/TMC.2006.153]
• 11: Marios Hadjieleftheriou , George Kollios , J. Tsotras , Dimitrios Gunopulos, Indexing spatiotemporal archives, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.143-164, June 2006 [doi>10.1007/s00778-004-0151-3]
• 12: Haibo Hu , Jianliang Xu , Dik Lun Lee, A generic framework for monitoring continuous spatial queries over moving objects, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066212]
• 13: H. Imai and M. Iri. An optimal algorithm for approximating a piecewise linear function. Journal of Information Processing, 9(3):169--162, 1986.
• 14: C. S. Jensen, D. Lin, and B. C. Ooi. Continuous clustering of moving objects. IEEE Transactions on Knowledge and Data Engineering, 19(9):1161--1174, 2007.
• 15: P. Kalnis, N. Mamoulis, and S. Bakiras. On discovering moving clusters in spatio-temporal data. In International Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 364--381, 2005.
• 16: Jae-Gil Lee , Jiawei Han , Kyu-Young Whang, Trajectory clustering: a partition-and-group framework, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247546]
• 17: X. Li, J. Han, J.-G. Lee, and H. Gonzalez. Traffic density-based discovery of hot routes in road networks. In International Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 441--459, 2007.
• 18: Yifan Li , Jiawei Han , Jiong Yang, Clustering moving objects, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014129]
• 19: Nikos Mamoulis , Huiping Cao , George Kollios , Marios Hadjieleftheriou , Yufei Tao , David W. Cheung, Mining, indexing, and querying historical spatiotemporal data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014080]
• 20: N. Meratnia and R. A. de By. Spatiotemporal compression techniques for moving point objects. In International Conference on Extending Database Technology (EDBT), pages 765--782, 2004.
• 21: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 22: S. Papadopoulos, D. Sacharidis, and K. Mouratidis. Continuous medoid queries over moving objects. In International Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 38--56, 2007.
• 23: Michalis Potamias , Kostas Patroumpas , Timos Sellis, Sampling Trajectory Streams with Spatiotemporal Criteria, Proceedings of the 18th International Conference on Scientific and Statistical Database Management, p.275-284, July 03-05, 2006 [doi>10.1109/SSDBM.2006.45]
• 24: Sunil Prabhakar , Yuni Xia , Dmitri V. Kalashnikov , Walid G. Aref , Susanne E. Hambrusch, Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects, IEEE Transactions on Computers, v.51 n.10, p.1124-1140, October 2002 [doi>10.1109/TC.2002.1039840]
• 25: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 26: Michail Vlachos , Dimitrios Gunopoulos , George Kollios, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 27: W. Wu, W. Guo, and K.-L. Tan. Distributed processing of moving k-nearest-neighbor query on moving objects. In IEEE International Conference on Data Engineering (ICDE), pages 1116--1125, 2007.
• 28: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems