research-article

Route planning for locations based on trajectory segments

Authors:

Jinsheng Jiang,

Kaiwei KongAuthors Info & Claims

UrbanGIS '16: Proceedings of the 2nd ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics

Article No.: 6, Pages 1 - 8

https://doi.org/10.1145/3007540.3007546

Published: 31 October 2016 Publication History

Abstract

Route planning for a set of locations based on trajectory searching is a hot topic. To obtain previous drivers' knowledge on route selection, some existing works search trajectories which are spatially close to the query locations. However, these trajectories may be only close to partial query locations or go to other locations beyond the query location set, which lead the algorithm to a poor performance. In this paper, we study a new model called Route Planning for Locations Based on Trajectory Segment (RPBTS). Given a set of ordered query locations, in order to pass as close as to the query locations, we plan a route by combining some intersecting trajectory segments. A greedy algorithm is employed to retrieve the optimal combinations which doesn't contain the two undesirable conditions mentioned above. To enhance the performance of the algorithm, we construct a regional landmark graph, where a regional landmark is a road segment frequently traversed by drivers in a certain region. Based on this graph, it's very likely a query location can be converted to a regional landmark. Finally, we propose a Random Selection strategy to further improve the efficiency. The effectiveness of our method is verified by empirical study based on a real trajectory data set.

References

[1]

R. Bellman. On a routing problem. Technical report, DTIC Document, 1956.

[2]

Z. Chen, H. T. Shen, and X. Zhou. Discovering popular routes from tajectories. In ICDE, pages 900--911. IEEE, 2011.

Digital Library

[3]

Z. Chen, H. T. Shen, X. Zhou, Y. Zheng, and X. Xie. Searching trajectories by locations: an efficiency study. In SIGMOD, pages 255--266. ACM, 2010.

Digital Library

[4]

J. Dai, B. Yang, C. Guo, and Z. Ding. Personalized route recommendation using big trajectory data. In ICDE, pages 543--554. IEEE, 2015.

[5]

D. Delling, A. V. Goldberg, M. Goldszmidt, J. Krumm, K. Talwar, and R. F. Werneck. Navigation made personal: inferring driving preferences from GPS traces. In SIGSPATIAL, pages 31:1--31:9, 2015.

Digital Library

[6]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269--271, 1959.

Digital Library

[7]

B. Ding, J. X. Yu, and L. Qin. Finding time-dependent shortest paths over large graphs. In EDBT, pages 205--216. ACM, 2008.

Digital Library

[8]

C. Guo, Y. Ma, B. Yang, C. S. Jensen, and M. Kaul. Ecomark: evaluating models of vehicular environmental impact. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pages 269--278. ACM, 2012.

Digital Library

[9]

E. Kanoulas, Y. Du, T. Xia, and D. Zhang. Finding fastest paths on a road network with speed patterns. In ICDE, pages 10--10. IEEE, 2006.

Digital Library

[10]

T. Li and S. S. Anand. Diva: a variance-based clustering approach for multi-type relational data. In CIKM, pages 147--156, 2007.

Digital Library

[11]

Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching for low-sampling-rate gps trajectories. In SIGSPATIAL, pages 352--361. ACM, 2009.

Digital Library

[12]

W. Luo, H. Tan, L. Chen, and L. M. Ni. Finding time period-based most frequent path in big trajectory data. In SIGMOD, pages 713--724. ACM, 2013.

Digital Library

[13]

S. Qi, P. Bouros, D. Sacharidis, and N. Mamoulis. Efficient point-based trajectory search. In SSTD, pages 179--196. Springer, 2015.

[14]

S. Shang, R. Ding, B. Yuan, K. Xie, K. Zheng, and P. Kalnis. User oriented trajectory search for trip recommendation. In EDBT, pages 156--167. ACM, 2012.

Digital Library

[15]

L.-A. Tang, Y. Zheng, X. Xie, J. Yuan, X. Yu, and J. Han. Retrieving k-nearest neighboring trajectories by a set of point locations. In SSTD, pages 223--241. Springer, 2011.

Digital Library

[16]

J. Yuan, Y. Zheng, X. Xie, and G. Sun. Driving with knowledge from the physical world. In SIGKDD, pages 316--324. ACM, 2011.

Digital Library

[17]

J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In SIGSPATIAL, pages 99--108. ACM, 2010.

Digital Library

[18]

K. Zheng, S. Shang, N. J. Yuan, and Y. Yang. Towards efficient search for activity trajectories. In ICDE, pages 230--241. IEEE, 2013.

Digital Library

Cited By

Jiang HTong SZhu RWei B(2024)RNDLP: A Distributed Framework for Supporting Continuous k-Similarity Trajectories Search over Road NetworkMathematics10.3390/math1202027012:2(270)Online publication date: 14-Jan-2024
https://doi.org/10.3390/math12020270
Ara Ghoreishi SMoshfeghi SJan MConniff JYang KJang JFurht BTappen RNewman DRosselli MZhai J(2023)Anomalous Behavior Detection in Trajectory Data of Older Drivers2023 IEEE 20th International Conference on Smart Communities: Improving Quality of Life using AI, Robotics and IoT (HONET)10.1109/HONET59747.2023.10374878(146-151)Online publication date: 4-Dec-2023
https://doi.org/10.1109/HONET59747.2023.10374878
Zhu RXiao MWang BYang XXia XZong CQiu T(2023)Continuous k-Similarity Trajectories Search over Data StreamDatabase Systems for Advanced Applications10.1007/978-3-031-30637-2_18(273-282)Online publication date: 14-Apr-2023
https://doi.org/10.1007/978-3-031-30637-2_18
Show More Cited By

Index Terms

Route planning for locations based on trajectory segments
1. Information systems
  1. Information systems applications
    1. Spatial-temporal systems
      1. Global positioning systems
2. Networks
  1. Network services
    1. Location based services

Recommendations

On route planning by inferring visiting time, modeling user preferences, and mining representative trip patterns

Location-based services allow users to perform check-in actions, which record the geo-spatial activities and provide a plentiful source to do more accurate and useful geographical recommendation. In this paper, we present a novel PreferredTime-aware ...
Trajectory Query Based on Trajectory Segments with Activities
UrbanGIS'17: Proceedings of the 3rd ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics

Searching trajectories with activities has attracted much attention in the last decade. Existing studies tend to find trajectories with activities matched to the required keywords. However, returned trajectories may have a satisfying textual matching ...
Optimizing Taxi Route Planning Based on Taxi Trajectory Data Analysis
Databases Theory and Applications
Abstract
In daily life, taxis have become one of the most common and convenient ways of public transportation. With the advancement of positioning and mobility technologies, a large amount of taxi trajectory data has been collected, providing valuable data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

UrbanGIS '16: Proceedings of the 2nd ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics

October 2016

67 pages

ISBN:9781450345835

DOI:10.1145/3007540

Conference Chair:
Huy T. Vo

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSPATIAL'16

SIGSPATIAL'16: 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

October 31, 2016

California, Burlingame

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang HTong SZhu RWei B(2024)RNDLP: A Distributed Framework for Supporting Continuous k-Similarity Trajectories Search over Road NetworkMathematics10.3390/math1202027012:2(270)Online publication date: 14-Jan-2024
https://doi.org/10.3390/math12020270
Ara Ghoreishi SMoshfeghi SJan MConniff JYang KJang JFurht BTappen RNewman DRosselli MZhai J(2023)Anomalous Behavior Detection in Trajectory Data of Older Drivers2023 IEEE 20th International Conference on Smart Communities: Improving Quality of Life using AI, Robotics and IoT (HONET)10.1109/HONET59747.2023.10374878(146-151)Online publication date: 4-Dec-2023
https://doi.org/10.1109/HONET59747.2023.10374878
Zhu RXiao MWang BYang XXia XZong CQiu T(2023)Continuous k-Similarity Trajectories Search over Data StreamDatabase Systems for Advanced Applications10.1007/978-3-031-30637-2_18(273-282)Online publication date: 14-Apr-2023
https://doi.org/10.1007/978-3-031-30637-2_18
Yuan HLi G(2019)Distributed In-memory Trajectory Similarity Search and Join on Road Network2019 IEEE 35th International Conference on Data Engineering (ICDE)10.1109/ICDE.2019.00115(1262-1273)Online publication date: Apr-2019
https://doi.org/10.1109/ICDE.2019.00115
Kong KXu JXu MTu LWu YChen Z(2017)Trajectory Query Based on Trajectory Segments with ActivitiesProceedings of the 3rd ACM SIGSPATIAL Workshop on Smart Cities and Urban Analytics10.1145/3152178.3152180(1-8)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3152178.3152180

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents