The popularity of location-aware devices has boosted urban systems with massive volumes of anonymous trajectory data, presenting both challenges and opportunities for enhancing smart city initiatives through Trajectory-User Linking (TUL). Typically, TUL aims to match anonymous trajectories with specific users by exploring spatiotemporal patterns and insightful mobility behaviors. However, current TUL models face significant limitations due to their reliance on singular data sources and insufficient consideration of real-world scenarios. Furthermore, these models often lack evaluation in fair and comprehensive environments, hindering accurate assessment of their performance and applicability. This paper systematically investigates prevalent challenges encountered by existing TUL models, conducts a comprehensive review of state-of-the-art models, and proposes a structured framework that encompasses three core components: point-level representation learning, trajectory-level representation learning, and user linking. Through meticulously designed experiments, we examine the effectiveness and efficiency of leading TUL models in handling the complexities of real-world data, such as data imbalance, sparsity, new users, and scalability. This in-depth analysis uncovers limitations in existing methodologies and offers guidance for future advancements, contributing to the development of robust TUL solutions for urban mobility analysis and smart city technologies.

As more detailed POI (Point of Interest) information has been incorporated into road network, routing has evolved from finding paths from one place to another, to satisfying users’ needs (keywords) along the trip. However, the existing solutions either only support one keyword per POI, or require a fixed visiting order, or only provide one option to choose from. Therefore, we study the top-k Optimal Routes with Collective Spatial Keywords (k-ORCSK) problem, which is the most general keyword-aware routing problem that supports multiple keywords, arbitrary orders, and top-k results. To solve this problem, we apply an enumeration framework and reduce the complexity by contracting non POI-related vertices and taking the keywords into account. After that, we propose a best-first path expansion method DA-CSK based on deviation to convert the enumeration paradigm from the distance-oriented to the keyword-oriented. Finally, several optimization techniques are provided to further improve the query efficiency. Extensive experiments conducted on multiple real-life road networks show that our method can provide higher quality results more efficiently.

Map-matching plays an essential role in many location-based applications. It seeks to translate a sequence of timestamped location measurements, which may originate from GPS, Bluetooth, or cellular sources, into the actual routes that moving objects follow on the underlying digital road network. Some existing work focus on map-matching methods based on Hidden Markov Models. While powerful, these methods are computationally demanding and require highly accurate location information. In contrast, neural network-based methods offer the ability to handle more complex data sources, but face challenges when applied to large-scale road networks. In this research, we delve into the task of map-matching using wireless traffic sensor data, specifically Bluetooth, in the context of expansive road networks. We introduce a Turn-Based Map-Matching (TBMM) model, built upon a Sequence-to-Sequence framework. This model accepts a sequence of Bluetooth readings as input and generates a sequence of successive turns with a predicted start road segment. As the sequence of turns is generated, the corresponding route is concurrently reconstructed, adhering to the topological structure of the underlying road network. Furthermore, we employ a two-step training approach to optimize our model. We begin by pre-training the model by minimizing cross-entropy loss. Subsequently, we deploy reinforcement learning to fine-tune the model, thereby further enhancing its performance. Our experimental study shows the promising performance of our TBMM model compared with two state-of-the-art solutions, achieving approximately 98% in precision, recall, and F1-score, demonstrating the potential of our approach in the domain of map-matching.

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.

The intelligent transportation systems, e.g., DiDi and Uber, have served as essential travel tools for customers, which foster plenty of studies for the location-based queries on road network. In particular, given a set O of objects and a query point q on a road network, the k Nearest Neighbor (kNN) query returns the k nearest objects in O with the shortest road network distance to q. In literature, most existing solutions for kNN queries tend to reduce the query time, indexing storage, or throughput of the kNN queries while overlooking the correctness of the queries caused by query-query and update-query conflicts. In our work, we propose a grid-based framework on conflict-aware kNN queries on moving objects which aims to optimize system throughput while guaranteeing query correctness. In particular, we first propose efficient index structures and new query algorithms that significantly improve the throughput. We further present novel scheduling algorithms that aim to avoid conflicts and improve the system throughput. Moreover, we devise approximate solutions that provide a controllable trade-off between the conflict of kNN queries and system throughput. Finally, we propose a cost-based dispatching strategy to assign the kNN results to the corresponding queries. Extensive experiments on real-world data demonstrate the effectiveness and efficiency of our proposed solutions over alternatives.

Route reconstruction targets at recovering the actual routes of objects moving on an underlying road network from their times-tamped position measurements. This fundamental pre-processing step to many location-based applications has been extensively studied for GPS data, which are object-centric and relatively densely sampled data. In this paper, we investigate the problem of route reconstruction using data collected from road-side Bluetooth scanners. In many cities, Bluetooth scanners are installed in road networks for monitoring the movement of Bluetooth-enabled devices. To address new challenges caused by such reader-centric Bluetooth data including spatial and temporal distortion, a new route reconstruction framework is proposed to transform Bluetooth readings through a family of distortion suppression strategies such that the transformed data can work well with the Hidden Markov model (HMM) map-matching approach. Extensive experiments are conducted to evaluate different transformation strategies with real-world datasets. The experimental results show that when the algorithm uses the baseline or the proposed transformation strategies, the map matching F1 score can be increased by up to 10% depending on the severity of distortion.

Given a set O of objects and a query point q on a road network, the k Nearest Neighbor (kNN) query returns the k nearest objects in O with the shortest road network distance to q. These kNN queries find many applications in location-based services, e.g., ride-hailing services, where each taxi is regarded as an object. In such applications, objects are constantly moving such that even for the same query point, the correct answer of a kNN query may vary with time. Ideally, the returned answer should be adequately correct with respect to the moving object set. However, in literature, all existing solutions for kNN queries mainly focus on reducing the query time, indexing storage, or throughput of the kNN queries with little focus on their correctness. Motivated by this, we propose a framework on correctness-aware kNN queries which aim to optimize system throughput while guaranteeing query correctness on moving objects. We formally define the serializable-kNN query that ensures the correctness of the query answer when considering moving objects and dependencies of different queries. We propose several techniques to optimize the throughput of serializable-kNN queries: firstly, we propose efficient index structures and new query algorithms that significantly improve the throughput; we further present novel scheduling algorithms that aim to avoid conflicts and improve the system throughput. Moreover, we devise approximate solutions that provide a controllable trade-off between the correctness of kNN queries and system throughput. Extensive experiments on real-world data demonstrate the effectiveness and efficiency of our proposed solutions over alternatives.

Given a pair of Origin-Destination (OD) locations, the set of trajectories passing from the original to destination, usually possesses the nature to reflect different traveling patterns between OD. In general, the higher diversity these trajectories have, the more various traveling behaviors and greater robustness of the connectivity can be revealed, which highly raises the value of transportation analysis towards the corresponding OD pair. Therefore, in this paper, we introduce a comprehensive and rational measure for trajectory diversity, on top of which we propose a novel query, Top-k Diversified Search (TkDS), that aims to find a set of k OD pairs among all the given OD pairs such that the trajectories traversing in-between have the highest diversity. Owing to the intrinsic characteristics of trajectory data, the computational cost for diversity is considerably high. Thus we present an efficient bounding algorithm with early termination to filter the candidates that are impossible to contribute the result. Finally, we demonstrate some case studies for trajectory diversity on real world dataset and give a comprehensive performance evaluation on the Top-k Diversified Search.