Next Article in Journal
An Effective NoSQL-Based Vector Map Tile Management Approach
Previous Article in Journal
Morphological PDEs on Graphs for Image Processing on Surfaces and Point Clouds
Article

Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks

1
State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China
2
Shenzhen Key Laboratory of Spatial Smart Sensing and Services, Shenzhen University, Shenzhen 518060, China
*
Author to whom correspondence should be addressed.
Academic Editor: Wolfgang Kainz
ISPRS Int. J. Geo-Inf. 2016, 5(11), 214; https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi5110214
Received: 13 September 2016 / Revised: 9 November 2016 / Accepted: 10 November 2016 / Published: 12 November 2016
The Space-time prism (STP) is a key concept in time geography for analyzing human activity-travel behavior under various Space-time constraints. Most existing time-geographic studies use a straightforward algorithm to construct STPs in road networks by using two one-to-all shortest path searches. However, this straightforward algorithm can introduce considerable computational overhead, given the fact that accessible links in a STP are generally a small portion of the whole network. To address this issue, an efficient geo-computational algorithm, called NTP-A*, is proposed. The proposed NTP-A* algorithm employs the A* and branch-and-bound techniques to discard inaccessible links during two shortest path searches, and thereby improves the STP construction performance. Comprehensive computational experiments are carried out to demonstrate the computational advantage of the proposed algorithm. Several implementation techniques, including the label-correcting technique and the hybrid link-node labeling technique, are discussed and analyzed. Experimental results show that the proposed NTP-A* algorithm can significantly improve STP construction performance in large-scale road networks by a factor of 100, compared with existing algorithms. View Full-Text
Keywords: Space-time prism (STP); road networks; geo-computational algorithm; time geography; big data analysis Space-time prism (STP); road networks; geo-computational algorithm; time geography; big data analysis
Show Figures

Figure 1

MDPI and ACS Style

Chen, H.-P.; Chen, B.Y.; Wang, Y.; Li, Q. Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks. ISPRS Int. J. Geo-Inf. 2016, 5, 214. https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi5110214

AMA Style

Chen H-P, Chen BY, Wang Y, Li Q. Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks. ISPRS International Journal of Geo-Information. 2016; 5(11):214. https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi5110214

Chicago/Turabian Style

Chen, Hui-Ping, Bi Y. Chen, Yafei Wang, and Qingquan Li. 2016. "Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks" ISPRS International Journal of Geo-Information 5, no. 11: 214. https://0-doi-org.brum.beds.ac.uk/10.3390/ijgi5110214

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Back to TopTop