Skip to main content
Erschienen in: World Wide Web 1/2017

07.09.2016

A feature based method for trajectory dataset segmentation and profiling

verfasst von: Wei Jiang, Jie Zhu, Jiajie Xu, Zhixu Li, Pengpeng Zhao, Lei Zhao

Erschienen in: World Wide Web | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The pervasiveness of location-acquisition and mobile computing techniques has generated massive spatial trajectory data, which has brought great challenges to the management and analysis of such a big data. In this paper, we focus on the sub-trajectory dataset profiling problem, and aim to extract the representative sub-trajectories from the raw trajectory as a subset, called profile, which can best describe the whole dataset. This problem is very challenging subject to finding the most representative sub-trajectories set by trading off the size and quality of the profile. To tackle this problem, we model the features of the trajectory dataset from the aspects of density, speed and the direction flow. Meanwhile we present our two-step method to select the representative trajectories based on the feature model. First, a novel trajectory segmentation algorithm is applied on a raw trajectory to identify the representative segments concerning their feature representativeness and automatically estimate the number of segments and the segment borders. Then, a sub-trajectory profiling method is performed to yield the most representative sub-trajectories in the dataset, based on a local heuristic evolution strategy. We evaluate our method based on extensive experiments by using two real-world trajectory datasets generated by over 12,000 taxicabs in Beijing and Shanghai. The results demonstrate the efficiency and effectiveness of our methods in different applications.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Chen, Z., Shen, H.T., Zhou, X.: Discovering popular routes from trajectories. In: 2011 IEEE 27th international conference on data engineering (ICDE), pp. 900–911. IEEE (2011) Chen, Z., Shen, H.T., Zhou, X.: Discovering popular routes from trajectories. In: 2011 IEEE 27th international conference on data engineering (ICDE), pp. 900–911. IEEE (2011)
2.
Zurück zum Zitat Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization 10(2), 112–122 (1973)CrossRef Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization 10(2), 112–122 (1973)CrossRef
3.
Zurück zum Zitat Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D.: Trajectory pattern mining. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 330–339. ACM (2007) Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D.: Trajectory pattern mining. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 330–339. ACM (2007)
4.
Zurück zum Zitat Hershberger, J.E., Snoeyink, J.: Speeding up the Douglas-Peucker line-simplification algorithm. University of British Columbia, Department of Computer Science (1992) Hershberger, J.E., Snoeyink, J.: Speeding up the Douglas-Peucker line-simplification algorithm. University of British Columbia, Department of Computer Science (1992)
5.
Zurück zum Zitat Jiang, W., Zhu, J., Xu, J., Li, Z., Zhao, P., Zhao, L.: Hv: a feature based method for trajectory dataset profiling, pp. 46–60. Springer (2015) Jiang, W., Zhu, J., Xu, J., Li, Z., Zhao, P., Zhao, L.: Hv: a feature based method for trajectory dataset profiling, pp. 46–60. Springer (2015)
7.
Zurück zum Zitat Lee, J.G., Han, J., Li, X.: Trajectory outlier detection: a partition-and-detect framework. In: ICDE 2008. IEEE 24th International Conference on Data Engineering, 2008, pp. 140–149. IEEE (2008) Lee, J.G., Han, J., Li, X.: Trajectory outlier detection: a partition-and-detect framework. In: ICDE 2008. IEEE 24th International Conference on Data Engineering, 2008, pp. 140–149. IEEE (2008)
8.
Zurück zum Zitat Lee, J.G., Han, J., Whang, K.Y.: Trajectory clustering: a partition-and-group framework. In: Proceedings of the 2007 ACM SIGMOD international conference on management of data, pp. 593–604. ACM (2007) Lee, J.G., Han, J., Whang, K.Y.: Trajectory clustering: a partition-and-group framework. In: Proceedings of the 2007 ACM SIGMOD international conference on management of data, pp. 593–604. ACM (2007)
9.
Zurück zum Zitat Li, X., Han, J., Lee, J.G., Gonzalez, H.: Traffic density-based discovery of hot routes in road networks. In: Advances in spatial and temporal databases, pp. 441–459. Springer (2007) Li, X., Han, J., Lee, J.G., Gonzalez, H.: Traffic density-based discovery of hot routes in road networks. In: Advances in spatial and temporal databases, pp. 441–459. Springer (2007)
11.
Zurück zum Zitat Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., Huang, Y.: Map-matching for low-sampling-rate gps trajectories. In: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, pp. 352–361. ACM (2009) Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., Huang, Y.: Map-matching for low-sampling-rate gps trajectories. In: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, pp. 352–361. ACM (2009)
12.
Zurück zum Zitat Monreale, A., Pinelli, F., Trasarti, R., Giannotti, F.: Wherenext: a location predictor on trajectory pattern mining. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 637–646. ACM (2009) Monreale, A., Pinelli, F., Trasarti, R., Giannotti, F.: Wherenext: a location predictor on trajectory pattern mining. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 637–646. ACM (2009)
13.
Zurück zum Zitat Panagiotakis, C., Pelekis, N., Kopanakis, I., Ramasso, E., Theodoridis, Y.: Segmentation and sampling of moving object trajectories based on representativeness. IEEE Trans Knowl Data Eng 24(7), 1328–1343 (2012)CrossRef Panagiotakis, C., Pelekis, N., Kopanakis, I., Ramasso, E., Theodoridis, Y.: Segmentation and sampling of moving object trajectories based on representativeness. IEEE Trans Knowl Data Eng 24(7), 1328–1343 (2012)CrossRef
14.
Zurück zum Zitat Pelekis, N., Kopanakis, I., Panagiotakis, C., Theodoridis, Y.: Unsupervised trajectory sampling. In: Machine learning and knowledge discovery in databases, pp. 17–33. Springer (2010) Pelekis, N., Kopanakis, I., Panagiotakis, C., Theodoridis, Y.: Unsupervised trajectory sampling. In: Machine learning and knowledge discovery in databases, pp. 17–33. Springer (2010)
15.
Zurück zum Zitat Sacharidis, D., Patroumpas, K., Terrovitis, M., Kantere, V., Potamias, M., Mouratidis, K., Sellis, T.: On-line discovery of hot motion paths. In: Proceedings of the 11th international conference on Extending database technology: Advances in database technology, pp. 392–403. ACM (2008) Sacharidis, D., Patroumpas, K., Terrovitis, M., Kantere, V., Potamias, M., Mouratidis, K., Sellis, T.: On-line discovery of hot motion paths. In: Proceedings of the 11th international conference on Extending database technology: Advances in database technology, pp. 392–403. ACM (2008)
16.
Zurück zum Zitat Taylor, K.M., Procopio, M.J., Young, C.J., Meyer, F.G.: Estimation of arrival times from seismic waves: a manifold-based approach. Geophys. J. Int. 185(1), 435–452 (2011)CrossRef Taylor, K.M., Procopio, M.J., Young, C.J., Meyer, F.G.: Estimation of arrival times from seismic waves: a manifold-based approach. Geophys. J. Int. 185(1), 435–452 (2011)CrossRef
17.
Zurück zum Zitat Trajcevski, G., Cao, H., Scheuermanny, P., Wolfsonz, O., Vaccaro, D.: On-line data reduction and the quality of history in moving objects databases. In: Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access, pp. 19–26. ACM (2006) Trajcevski, G., Cao, H., Scheuermanny, P., Wolfsonz, O., Vaccaro, D.: On-line data reduction and the quality of history in moving objects databases. In: Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access, pp. 19–26. ACM (2006)
18.
Zurück zum Zitat Wang, W., Yin, H., Chen, L., Sun, Y., Sadiq, S., Zhou, X.: Geo-sage: A geographical sparse additive generative model for spatial item recommendation. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1255–1264. ACM (2015) Wang, W., Yin, H., Chen, L., Sun, Y., Sadiq, S., Zhou, X.: Geo-sage: A geographical sparse additive generative model for spatial item recommendation. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1255–1264. ACM (2015)
19.
Zurück zum Zitat Wang, Y., Zheng, Y., Xue, Y.: Travel time estimation of a path using sparse trajectories. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 25–34. ACM (2014) Wang, Y., Zheng, Y., Xue, Y.: Travel time estimation of a path using sparse trajectories. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 25–34. ACM (2014)
20.
Zurück zum Zitat Wei, L.Y., Zheng, Y., Peng, W.C.: Constructing popular routes from uncertain trajectories. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 195–203. ACM (2012) Wei, L.Y., Zheng, Y., Peng, W.C.: Constructing popular routes from uncertain trajectories. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 195–203. ACM (2012)
21.
Zurück zum Zitat Xue, A.Y., Zhang, R., Zheng, Y., Xie, X., Huang, J., Xu, Z.: Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In: 2013 IEEE 29th international conference on data engineering (ICDE), pp. 254–265. IEEE (2013) Xue, A.Y., Zhang, R., Zheng, Y., Xie, X., Huang, J., Xu, Z.: Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In: 2013 IEEE 29th international conference on data engineering (ICDE), pp. 254–265. IEEE (2013)
22.
Zurück zum Zitat Yin, H., Cui, B., Chen, L., Hu, Z., Zhang, C.: Modeling location-based user rating profiles for personalized recommendation. ACM Trans. Knowl. Discovery Data (TKDD) 9(3), 19 (2015) Yin, H., Cui, B., Chen, L., Hu, Z., Zhang, C.: Modeling location-based user rating profiles for personalized recommendation. ACM Trans. Knowl. Discovery Data (TKDD) 9(3), 19 (2015)
23.
Zurück zum Zitat Yin, H., Cui, B., Huang, Z., Wang, W., Wu, X., Zhou, X.: Joint modeling of users’ interests and mobility patterns for point-of-interest recommendation. In: Proceedings of the 23rd annual ACM conference on multimedia conference, pp. 819–822. ACM (2015) Yin, H., Cui, B., Huang, Z., Wang, W., Wu, X., Zhou, X.: Joint modeling of users’ interests and mobility patterns for point-of-interest recommendation. In: Proceedings of the 23rd annual ACM conference on multimedia conference, pp. 819–822. ACM (2015)
24.
Zurück zum Zitat Yin, H., Cui, B., Zhou, X., Wang, W., Huang, Z., Sadiq, S.: Joint modeling of user check-in behaviors for real-time point-of-interest recommendation. ACM Trans. Inf. Syst. (2016) Yin, H., Cui, B., Zhou, X., Wang, W., Huang, Z., Sadiq, S.: Joint modeling of user check-in behaviors for real-time point-of-interest recommendation. ACM Trans. Inf. Syst. (2016)
25.
Zurück zum Zitat Yin, H., Hu, Z., Zhou, X., Wang, H., Zheng, K., Nguyen, Q.V.H., Sadiq, S.: Discovering interpretable geo-social communities for user behavior prediction Yin, H., Hu, Z., Zhou, X., Wang, H., Zheng, K., Nguyen, Q.V.H., Sadiq, S.: Discovering interpretable geo-social communities for user behavior prediction
26.
Zurück zum Zitat Yuan, J., Zheng, Y., Xie, X., Sun, G.: T-drive: Enhancing driving directions with taxi drivers’ intelligence. IEEE Trans. Knowl. Data Eng. 25(1), 220–232 (2013)CrossRef Yuan, J., Zheng, Y., Xie, X., Sun, G.: T-drive: Enhancing driving directions with taxi drivers’ intelligence. IEEE Trans. Knowl. Data Eng. 25(1), 220–232 (2013)CrossRef
27.
Zurück zum Zitat Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., Huang, Y.: T-drive: driving directions based on taxi trajectories. In: Proceedings of the 18th SIGSPATIAL international conference on advances in geographic information systems, pp. 99–108. ACM (2010) Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., Huang, Y.: T-drive: driving directions based on taxi trajectories. In: Proceedings of the 18th SIGSPATIAL international conference on advances in geographic information systems, pp. 99–108. ACM (2010)
28.
Zurück zum Zitat Yuan, N.J., Zheng, Y., Zhang, L., Xie, X.: T-finder: A recommender system for finding passengers and vacant taxis. IEEE Trans. Knowl. Data Eng. 25(10), 2390–2403 (2013)CrossRef Yuan, N.J., Zheng, Y., Zhang, L., Xie, X.: T-finder: A recommender system for finding passengers and vacant taxis. IEEE Trans. Knowl. Data Eng. 25(10), 2390–2403 (2013)CrossRef
29.
Zurück zum Zitat Zheng, Y., Chen, Y., Li, Q., Xie, X., Ma, W.Y.: Understanding transportation modes based on gps data for web applications. ACM Trans. Web (TWEB) 4(1), 1 (2010)CrossRef Zheng, Y., Chen, Y., Li, Q., Xie, X., Ma, W.Y.: Understanding transportation modes based on gps data for web applications. ACM Trans. Web (TWEB) 4(1), 1 (2010)CrossRef
30.
Zurück zum Zitat Zheng, Y., Zhang, L., Xie, X., Ma, W.Y.: Mining interesting locations and travel sequences from gps trajectories. In: Proceedings of the 18th international conference on World wide web, pp. 791–800. ACM (2009) Zheng, Y., Zhang, L., Xie, X., Ma, W.Y.: Mining interesting locations and travel sequences from gps trajectories. In: Proceedings of the 18th international conference on World wide web, pp. 791–800. ACM (2009)
31.
Zurück zum Zitat Zheng, K., Zheng, Y., Yuan, N.J., Shang, S.: On discovery of gathering patterns from trajectories. In: 2013 IEEE 29th international conference on data engineering (ICDE), pp. 242–253. IEEE (2013) Zheng, K., Zheng, Y., Yuan, N.J., Shang, S.: On discovery of gathering patterns from trajectories. In: 2013 IEEE 29th international conference on data engineering (ICDE), pp. 242–253. IEEE (2013)
Metadaten
Titel
A feature based method for trajectory dataset segmentation and profiling
verfasst von
Wei Jiang
Jie Zhu
Jiajie Xu
Zhixu Li
Pengpeng Zhao
Lei Zhao
Publikationsdatum
07.09.2016
Verlag
Springer US
Erschienen in
World Wide Web / Ausgabe 1/2017
Print ISSN: 1386-145X
Elektronische ISSN: 1573-1413
DOI
https://doi.org/10.1007/s11280-016-0396-y

Weitere Artikel der Ausgabe 1/2017

World Wide Web 1/2017 Zur Ausgabe