Approximate Nearest Neighbor (ANN) search is a foundational yet computationally demanding query in vector databases, critical for applications such as information retrieval and generative AI inference. Hierarchical graph-based methods have attracted significant attention due to their promising query performances compared to other indexes for ANN search. However, these methods still face efficiency bottlenecks because they rely on exhaustive and level-by-level traversals within hierarchical graphs. This paper introduces SHG, a novel hierarchical graph-based index that enhances search efficiency by bypassing intermediate and redundant levels. Specifically, SHG leverages a hierarchical vector compression method to reduce the time spent on distance computations, and employs a new data structure called shortcuts to determine the number of intermediate levels that can be safely skipped. Extensive experiments demonstrate that our solution achieves 1.5–1.8× speedup compared to state-of-the-art methods. Meanwhile, our method significantly improves the robustness of ANN search, boosting recall by up to 20% for certain queries on benchmark datasets.

Querying the shortest path between two locations is a fundamental task in many applications, and has been extensively studied for static road networks. However, in reality, the travel costs of road segments evolve over time, and hence the road network can be modeled as a time-dependent graph. In this paper, we study the shortest path query over large-scale time-dependent road networks. We first present a tree decomposition method to model the time-dependent road network as a tree structure that preserves travel costs. To further improve query efficiency, a set of shortcuts is selected and built on the constructed tree structure. Specifically, we formally define a shortcut selection problem over the tree decomposition of the time-dependent road network. This problem, which is proven to be NP-hard, aims to select and build the most effective shortcut set. We first devise a dynamic programming method with exact results to solve the selection problem. To obtain the optimal shortcut set quickly, we design an approximation algorithm that guarantees a 0.5-approximation ratio. Based on the novel tree structure, we devise a shortcut-based algorithm to answer the shortest path query over time-dependent road networks. Finally, we conduct extensive performance studies using large-scale real-world road networks. The results demonstrate that our method can achieve better efficiency and scalability than the state-of-the-art method.

One of the most important challenges in shared mobility services ( e.g. , ride-sharing and parcel delivery) is planning routes for workers by considering real road conditions. To tackle this challenge, the "insertion operator", which computes the optimal route for the worker to serve ( i.e. , insert) the newly appeared delivery request, has been acted as the fundamental operation in existing solutions. However, existing works implicitly assume a static road network, hence are hard to fulfill the real-world scenario, where travel time between two locations is not constant at different times of a day. By contrast, we focus on the insertion operator over time-dependent road networks that capture the periodic pattern of road conditions. We also show that the time complexity of existing solutions would degrade into cubic time and hence such solutions can no longer satisfy the real-time requirement under this real-world setting. To satisfy the need for real-time computation, we propose a data summary to model the time-dependent travel time functions between pairs of vertices in the route. Based on the data summary, we design an efficient solution that can enumerate the best insertion position in linear time while satisfying complex spatiotemporal constraints. Finally, extensive experiments are conducted on real datasets from several applications of shared mobility. The results show that our solution is up to 44.5X faster than the state-of-the-art solution.

Taxi ridesharing becomes promising and attractive because of the wide availability of taxis in a city and tremendous benefits of ridesharing, e.g., alleviating traffic congestion and reducing energy consumption. Existing taxi ridesharing schemes, however, are not efficient and practical, due to they simply match ride requests and taxis based on partial trip information and omit the offline passengers, who hail a taxi at roadside with no explicit requests to the system. In this paper, we consider the mobility-aware taxi ridesharing problem, and present mT- Share to address these limitations. mT-Share fully exploits the mobility information of ride requests and taxis to achieve efficient indexing of taxis/requests and better passenger-taxi matching, while still satisfying the constraints on passengers' deadlines and taxis' capacities. Specifically, mT-Share indexes taxis and ride requests with both geographical information and travel directions, and supports the shortest path based routing and probabilistic routing to serve both online and offline ride requests. Extensive experiments with a large real-world taxi dataset demonstrate the efficiency and effectiveness of mT-Share, which can response each ride request in milliseconds and with a moderate detour cost. Compared to state-of-the-art methods, mT-Share serves 42% and 62% more ride requests in peak and non-peak hours, respectively.