Lei Li

Lei Li

Auto-generated profile, based on publicly available information

Lei Li

The Hong Kong University of Science and Technology

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
21 March 2018 in The VLDB Journal
Verified
Journal Article
Closed access
PDF file
LLLei Li
Lei Li
KZKai Zheng
Kai Zheng
SWSibo Wang
Sibo Wang
WHWen Hua
Wen Hua
XZXiaofang Zhou
Xiaofang Zhou

1 April 2020
Verified
Conference Paper
Closed access
LLLei Li
Lei Li
MZMengxuan Zhang
Mengxuan Zhang
WHWen Hua
Wen Hua
XZXiaofang Zhou
Xiaofang Zhou
Shortest path query is a fundamental operation in various location-based services (LBS) and most of them process queries on the server-side. As the business expands, scalability becomes a severe issue. Instead of simply deploying more servers to cope with the quickly increasing query number, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this paper, we aim to improve the performance of batch shortest path algorithms by revisiting the problem of query clustering. Specifically, we first propose three query decomposition methods to cluster queries: Zigzag that considers the 1-N shared computation; Search-Space Estimation that further incorporates search space estimation; and Co-Clustering that considers the source and target’s spatial locality. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: Local Cache that improves the existing Global Cache with higher cache hit ratio, and R2R that finds a set of approximate shortest paths from one region to another with bounded error. Experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

1 August 2017 in Proceedings of the VLDB Endowment
Verified
Journal Article
Open access
PDF file
LLLei Li
Lei Li
WHWen Hua
Wen Hua
XDXingzhong Du
Xingzhong Du
XZXiaofang Zhou
Xiaofang Zhou
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 example, 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.

1 April 2019
Verified
Conference Paper
Closed access
LLLei Li
Lei Li
SWSibo Wang
Sibo Wang
XZXiaofang Zhou
Xiaofang Zhou
Route scheduling on time-dependent road network is slow due to its problem complexity of Ω(T(|V|log |V|+|E|)), where T is the size of the result's time-dependent function, |V| is the number of vertices and |E| is the number of edges. To make things worse, T grows larger as the route becomes longer or the query time interval becomes bigger, especially for a fastest path profile query whose time interval is 24 hours. In this paper, we aim to answer the fastest path profile query on time-dependent road network faster by extending the 2-hop labeling approach, which is fast in answering shortest distance query on the static graph. However, building an index on a time-dependent graph is both time and space consuming, so currently only online-search approach exist. Apparently, its query answering power is limited by the online searching. To solve this problem, we first propose the time-dependent hop on large road network by partitioning it into smaller sub-graphs. The index is built within and between the partitions, and is retrieved from disk during query answering with the help of sampling. Moreover, we propose an online approximation technique AT-Dijkstra and a bottom-up compression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.

18 March 2020 in IEEE Transactions on Knowledge and Data Engineering
Verified
Journal Article
Closed access
LLLei Li
Lei Li
SWSibo Wang
Sibo Wang
XZXiaofang Zhou
Xiaofang Zhou
Finding the fastest path in the time-dependent road network is time consuming because its problem complexity is $\Omega(T(|V|\log|V| + |E|))$ , where $T$ is the size of the result's time-dependent function, $|V|$ and $|E|$ are the number of vertices and edges. There are three kinds of fastest path problems: SSFP (Single-Staring Time Fastest Path) that has a fixed departure time, ISFP (Interval-Staring Time Fastest Path) that selects the best departure time from an interval, and FPP (Fastest Path Profile) that returns the travel time of the entire time domain. In this paper, we aim to answer these three queries in time-dependent road network faster by extending the 2-hop labeling approach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index for SSFP and ISFP because there are $T$ and $|T|^2$ possible time points and intervals, where $T$ is the time domain. Therefore, we first propose the time-dependent hop-labeling for FPP, then provide the specific optimizations for SSFP and ISFP query answering. Moreover, it is both time and space consuming to build an index in a large time-dependent graph, so we partition road network into smaller sub-graphs and build indexes within and between the partitions. Furthermore, we propose an online approximation technique AT-Dijkstra and a bottom-up compression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.

27 July 2022 in The VLDB Journal
Verified
Journal Article
Open access
PDF file
JLJiajia Li
Jiajia Li
CNCancan Ni
Cancan Ni
DHDan He
Dan He
LLLei Li
Lei Li
XXXiufeng Xia
Xiufeng Xia
XZXiaofang Zhou
Xiaofang Zhou
In this paper, we study the Time-Dependent k Nearest Neighbor (TD-kNN) 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 kNN query on moving objects has been widely studied in the scenario of the static road network, the TD-kNN 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-kNN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable kNN (TD-AkNN) 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-kNN and TD-AkNN queries are superior to the competitors in orders of magnitude.