Hoyoung Jeung
Christian S. Jensen
Abstract
As mobile devices with positioning capabilities continue to proliferate, data management for so-called trajectory databases that capture the historical movements of populations of moving objects becomes important. This paper considers the querying of such databases for convoys, a convoy being a group of objects that have traveled together for some time.
More specifically, this paper formalizes the concept of a convoy query using density-based notions, in order to capture groups of arbitrary extents and shapes. Convoy discovery is relevant for real-life applications in throughput planning of trucks and carpooling of vehicles. Although there has been extensive research on trajectories in the literature, none of this can be applied to retrieve correctly exact convoy result sets. Motivated by this, we develop three efficient algorithms for convoy discovery that adopt the well-known filter-refinement framework. In the filter step, we apply line-simplification techniques on the trajectories and establish distance bounds between the simplified trajectories. This permits efficient convoy discovery over the simplified trajectories without missing any actual convoys. In the refinement step, the candidate convoys are further processed to obtain the actual convoys. Our comprehensive empirical study offers insight into the properties of the paper's proposals and demonstrates that the proposals are effective and efficient on real-world trajectory data.
- Inrix, Inc. Smart Dust Network. http://www.inrix.com/techdustnetwork.asp.Google Scholar
- http://www.rtreeportal.org/Google Scholar
- http://daisy.aau.dk/Google Scholar
- H. Jeung, H. T. Shen, and X. Zhou. Convoy Queries in Spatio-Temporal Databases. In ICDE, pp. 1457--1459, 2008. Google ScholarDigital Library
- G. Al-Naymat, S. Chawla, and J. Gudmundsson. Dimensionality reduction of long duration and complex spatio-temporal queries. In ACM SAC, pp. 393--397, 2007. Google ScholarDigital Library
- S. Arumugam and C. Jermaine. Closest-point-of-approach join for moving object histories. In ICDE, p. 86, 2006. Google ScholarDigital Library
- P. Bakalov, M. Hadjieleftheriou, and V. J. Tsotras. Time relaxed spatiotemporal trajectory joins. In ACM GIS, pp. 182--191, 2005. Google ScholarDigital Library
- H. Cao, O. Wolfson, and G. Trajcevski. Spatio-temporal data reduction with deterministic error bounds. VLDBJ, 15(3): 211--228, 2006. Google ScholarDigital Library
- L. Chen and R. T. Ng. On the marriage of Ip-norms and edit distance. In VLDB, pp. 792--803, 2004. Google ScholarDigital Library
- L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. In SIGMOD, pp. 491--502, 2005. Google ScholarDigital Library
- D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a line or its character. The American Cartographer, 10(42):112--123, 1973.Google ScholarCross Ref
- M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In SIGKDD, pp. 226--231, 1996.Google ScholarDigital Library
- J. Gudmundsson and M. van Kreveld. Computing longest duration flocks in trajectory data. In ACM GIS, pp. 35--42, 2006. Google ScholarDigital Library
- J. Gudmundsson, M. van Kreveld, and B. Speckmann. Efficient detection of motion patterns in spatio-temporal data sets. In ACM GIS, pp. 250--257, 2004. Google ScholarDigital Library
- D. Gunopoulos. Discovering similar multidimensional trajectories. In ICDE, pp. 673--684, 2002. Google ScholarDigital Library
- J. Hershberger and J. Snoeyink. Speeding up the douglas-peucker line-simplification algorithm. In International Symposium on Spatial Data Handling, pp. 134--143, 1992.Google Scholar
- C. S. Jensen, D. Lin, and B. C. Ooi. Continuous clustering of moving objects. IEEE TKDE, 19(9): 1161--1174, 2007. Google ScholarDigital Library
- S. Jeong, N. Paton, A. Fernandes, and T. Griffiths. An experimental performance evaluation of spatiotemporal join strategies. Transactions in GIS, 9(2):129--156, 2005.Google ScholarCross Ref
- P. Kalnis, N. Mamoulis, and S. Bakiras. On discovering moving clusters in spatio-temporal data. In SSTD, pp. 364--381, 2005. Google ScholarDigital Library
- J. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: A partition-and-group framework. In SIGMOD, pp. 593--604, 2007. Google ScholarDigital Library
- Y. Li, J. Han, and J. Yang. Clustering moving objects. In SIGKDD, pp. 617--622, 2004. Google ScholarDigital Library
- Z. Li. An algorithm for compressing digital contour data. The Cartographic Journal, 25(2): 143--146, 1988.Google ScholarCross Ref
- N. Meratnia and R. A. de By. Spatiotemporal compression techniques for moving point objects. In EDBT, pp. 765--782, 2004.Google ScholarCross Ref
- M. Spiliopoulou, I. Ntoutsi, Y. Theodoridis, and R. Schult. Monic: modeling and monitoring cluster transitions. In SIGKDD, pp. 706--711, 2006. Google ScholarDigital Library
- B. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In ICDE, pp. 201--208, 1998. Google ScholarDigital Library
- P. Zhou, D. Zhang, B. Salzberg, G. Cooperman, and G. Kollios. Close pair queries in moving object databases. In ACM GIS, pp. 2--11, 2005. Google ScholarDigital Library
Index Terms
- Discovery of convoys in trajectory databases
Recommendations
Discovery of evolving convoys
SSDBM'10: Proceedings of the 22nd international conference on Scientific and statistical database managementTraditionally, a convoy is defined as a set of moving objects that are close to each other for a period of time. Existing techniques, following this traditional definition, cannot find evolving convoys with dynamic members and do not have any monitoring ...
Trajectory queries and octagons in moving object databases
CIKM '02: Proceedings of the eleventh international conference on Information and knowledge managementAn important class of queries in moving object databases involves trajectories. We propose to divide trajectory predicates into topological and non-topological parts; extend the 9 intersection model of Egenhofer-Franzosa to a 3-step evaluation strategy ...
The maximum trajectory coverage query in spatial databases
With the widespread use of GPS-enabled mobile devices, an unprecedented amount of trajectory data has become available from various sources such as Bikely, GPS-wayPoints, and Uber. The rise of smart transportation services and recent break-throughs in ...
Comments