Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/79949
Title: Probabilistic time-constrained paths search over uncertain road networks
Authors: Li, WG 
Guan, JH
Lian, X
Zhou, SG
Cao, JN 
Keywords: Location-based service
Uncertain road network
Service time-constrained POI
Path search
Issue Date: 2018
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on services computing, Mar.-Apr. 2018, v. 11, no. 2, p. 399-414 How to cite?
Journal: IEEE transactions on services computing 
Abstract: With the proliferation of positioning technologies and GPS-enabled mobile devices, it has become very important to search for optimal paths to cover required points of interest (POIs, e.g., banks and restaurants) over road networks in many location-based services. In practice, however, traffic conditions are inherently uncertain and dynamically changing over time, which makes it rather challenging to provide accurate results for path queries based on travelling time. Inspired by this, we consider the practical settings of road networks and model them by uncertain road networks (URNs) on which the travelling time of each road is uncertain and captured by a set of travelling time samples. Then, we formalize the probabilistic time-constrained path (PTP) query over uncertain road networks to retrieve those paths that not only cover required POIs with constrained service time but also have the minimum travelling times in high confidence. We prove that PTP query problem is NP-hard. In order to answer PTP queries efficiently, we propose an efficient PTP query approach with effective pruning strategies regarding the time constraints on POIs and the probabilistic/rank requirements of queries. Extensive experiments on real road networks validate the efficiency and effectiveness of our PTP query approach.
URI: http://hdl.handle.net/10397/79949
EISSN: 1939-1374
DOI: 10.1109/TSC.2016.2582692
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

1
Citations as of Jan 14, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.