Journal article
Mining Spatio-Temporal Reachable Regions With Multiple Sources over Massive Trajectory Data
IEEE transactions on knowledge and data engineering, Vol.33(7), pp.2930-2942
07/01/2021
DOI: 10.1109/TKDE.2019.2959531
Abstract
Given a set of user-specified locations and a massive trajectory dataset, the task of mining spatio-temporal reachable regions aims at finding which road segments are reachable from these locations within a given temporal period based on the historical trajectories. Determining such spatio-temporal reachable regions with high accuracy is vital for many urban applications, such as location-based recommendations and advertising. Traditional approaches to answering such queries essentially perform a distance-based range query over the given road network, which does not consider dynamic travel time at different time of day. By contrast, we propose a data-driven approach to formulate the problem as mining actual reachable regions based on a real historical trajectory dataset. Efficient algorithms for the Single-location spatio-temporal reachability Query (S-Query) and the Union-of-multi-location spatio-temporal reachability Query (U-Query) were presented in our recent work. In this paper, we extend the previous ideas by introducing a new type of reachability query with multiple sources, namely, the Intersection-of-multi-location spatio-temporal reachability Query (I-Query). As we demonstrate, answering I-Queries efficiently is generally more computationally challenging than answering either S-Queries or U-Queries because I-Queries involve complicated intersect conditions. We propose two new algorithms called the Intersection-of-Multi-location Query Maximum Bounding region search (I-MQMB) algorithm and the I-Query Trace Back Search (I-TBS) algorithm to efficiently answer I-Queries, which utilize an indexing schema composed of a spatio-temporal index and a connection index. We evaluate our system extensively by using a large-scale real taxi trajectory dataset that records taxi rides in Shenzhen, China. Our results demonstrate that the proposed approach reduces the running time of I-Queries by 50 percent on average compared to the baseline method.
Details
- Title: Subtitle
- Mining Spatio-Temporal Reachable Regions With Multiple Sources over Massive Trajectory Data
- Creators
- Yichen Ding - University of IowaXun Zhou - University of IowaGuojun Wu - Worcester Polytechnic InstituteYanhua Li - Worcester Polytechnic InstituteJie Bao - Urban Computing Business Unit, JD Finance, Beijing, ChinaYu Zheng - Southwest Jiaotong UniversityJun Luo - Lenovo Machine Intelligence Center, Hong Kong
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on knowledge and data engineering, Vol.33(7), pp.2930-2942
- Publisher
- IEEE
- DOI
- 10.1109/TKDE.2019.2959531
- ISSN
- 1041-4347
- eISSN
- 1558-2191
- Grant note
- CNS-1657350; CMMI-1831140 / National Science Foundation (10.13039/100000001) IIS-1566386 / National Science Foundation (10.13039/100000001) 2019YFB2101805 / National Key Research and Development Program of China (10.13039/501100012166) 61672399; U1609217 / National Natural Science Foundation of China; NSFC (10.13039/501100001809) DiDi Chuxing Inc.
- Language
- English
- Date published
- 07/01/2021
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380423102771
Metrics
9 Record Views