ORCID Profile
0000-0002-1386-767X
Current Organisations
Hong Kong University of Science and Technology
,
Guangzhou HKUST Fok Ying Tung Research Institute
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Association for Computing Machinery (ACM)
Date: 07-2022
Abstract: Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of ersifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we e into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.
Publisher: Springer Science and Business Media LLC
Date: 11-08-2022
Publisher: Association for Computing Machinery (ACM)
Date: 05-06-2018
Abstract: Navigation has been an important tool for human civilization for thousands of years, and the latest technologies like online map services and GPS satellites have brought it up to a new level. Now people can easily identify where we are on earth, find any places they want to go, and retrieve best routes to get there. Although there are plenty of tools that are convenient and fast enough for basic uses, it is still far from optimal. For ex le, most systems only consider various type of distances as the optimization goals, while the traveling time, which needs to consider traffic conditions, is a more appropriate one. However, it is both hard to acquire the traffic condition information and to compute time-dependent fastest paths. Therefore, in this article, we present an introduction to the time-dependent route scheduling, from speed profile generation to route scheduling and query answering.
Publisher: IEEE
Date: 04-2021
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2023
Publisher: Springer International Publishing
Date: 2020
Publisher: IEEE
Date: 04-2021
Publisher: Springer International Publishing
Date: 2016
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 02-2022
Publisher: IEEE
Date: 04-2023
Publisher: Springer Science and Business Media LLC
Date: 27-07-2022
DOI: 10.1007/S00778-022-00758-W
Abstract: In this paper, we study the Time-Dependent k Nearest Neighbor (TD- k NN) query on moving objects that aims to return k objects arriving at the query location with the least traveling cost departing at a given time t . Although the k NN query on moving objects has been widely studied in the scenario of the static road network, the TD- k NN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network. Additionally, we establish a grid index on moving objects for candidate object retrieval and location update. To further accelerate the TD- k NN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable k NN (TD-A k NN) query on moving objects targeting for the application of taxi-hailing service, where the moving object might have been occupied. Extensive experiments with different parameter settings on real-world road network show that our solutions for both TD- k NN and TD-A k NN queries are superior to the competitors in orders of magnitude.
Publisher: IEEE
Date: 04-2021
Publisher: Springer International Publishing
Date: 2014
Publisher: IEEE
Date: 06-2019
Publisher: IEEE
Date: 04-2020
Publisher: Springer International Publishing
Date: 2018
Publisher: Association for Computing Machinery (ACM)
Date: 08-2017
Abstract: On time-dependent graphs, fastest path query is an important problem and has been well studied. It focuses on minimizing the total travel time (waiting time + on-road time) but does not allow waiting on any intermediate vertex if the FIFO property is applied. However, in practice, waiting on a vertex can reduce the time spent on the road (for ex le, resuming traveling after a traffic jam). In this paper, we study how to find a path with the minimal on-road time on time-dependent graphs by allowing waiting on some predefined parking vertices. The existing works are based on the following fact: the arrival time of a vertex v is determined by the arrival time of its in-neighbor u , which does not hold in our scenario since we also consider the waiting time on u if u allows waiting. Thus, determining the waiting time on each parking vertex to achieve the minimal on-road time becomes a big challenge, which further breaks FIFO property. To cope with this challenging problem, we propose two efficient algorithms using minimum on-road travel cost function to answer the query. The evaluations on multiple real-world time-dependent graphs show that the proposed algorithms are more accurate and efficient than the extensions of existing algorithms. In addition, the results further indicate, if the parking facilities are enabled in the route scheduling algorithms, the on-road time will reduce significantly compared to the fastest path algorithms.
Publisher: IEEE
Date: 04-2023
Publisher: IEEE
Date: 04-2019
Publisher: Association for Computing Machinery (ACM)
Date: 07-2022
Abstract: Multi-Constraint Shortest Path ( MCSP ) generalizes the classic shortest path from single to multiple criteria such that more personalized needs can be satisfied. However, MCSP query is essentially a high-dimensional skyline problem and thus time-consuming to answer. Although the current Forest Hop Labeling (FHL) index can answer MCSP efficiently, it takes a long time to construct and lacks the flexibility to handle arbitrary criteria combinations. In this paper, we propose a skyline-cube-based FHL index that can handle the flexible MCSP efficiently. Firstly, we analyze the relation between low and high-dimensional skyline paths theoretically and use a cube to organize them hierarchically. After that, we propose methods to derive the high-dimensional path from the lower ones, which can adapt to the flexible scenario naturally and reduce the expensive high dimensional path concatenation. Then we introduce efficient methods for both single and multi-hop cube concatenations and propose pruning methods to further alleviate the computation. Finally, we improve the FHL structure with lower height for faster construction and query. Experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art.
Publisher: Springer International Publishing
Date: 2021
Publisher: Springer International Publishing
Date: 2016
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2020
Publisher: Springer International Publishing
Date: 2019
Publisher: Springer Science and Business Media LLC
Date: 03-09-2016
Publisher: Springer Nature Switzerland
Date: 2023
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 11-2023
Publisher: Springer Science and Business Media LLC
Date: 21-03-2018
Publisher: Springer International Publishing
Date: 2020
Publisher: Springer International Publishing
Date: 2021
Publisher: Springer International Publishing
Date: 2022
Publisher: IEEE
Date: 12-2020
DOI: 10.1109/ISPA-BDCLOUD-SOCIALCOM-SUSTAINCOM51426.2020.00103
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 05-2022
Publisher: Association for Computing Machinery (ACM)
Date: 07-2021
Abstract: Shortest path computation is a building block of various network applications. Since real-life networks evolve as time passes, the Dynamic Shortest Path (DSP) problem has drawn lots of attention in recent years. However, as DSP has many factors related to network topology, update patterns, and query characteristics, existing works only test their algorithms on limited situations without sufficient comparisons with other approaches. Thus, it is still hard to choose the most suitable method in practice. To this end, we first identify the determinant dimensions and constraint dimensions of the DSP problem and create a complete problem space to cover all possible situations. Then we evaluate the state-of-the-art DSP methods under the same implementation standard and test them systematically under a set of synthetic dynamic networks. Furthermore, we propose the concept of dynamic degree to classify the dynamic environments and use throughput to evaluate their performance. These results can serve as a guideline to find the best solution for each situation during system implementation and also identify research opportunities. Finally, we validate our findings on real-life dynamic networks.
No related grants have been discovered for Lei Li.