PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Trajectory Data Management, Analytics, and Learning

Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Gao Cong

arXiv:2003.11547v2cs.DB

TL;DR

Urban trajectory data is increasingly collected through GPS-equipped devices and location-based services, creating demand for efficient management and analysis. This survey organizes research across trajectory processing, storage, analytics, clustering, real-time applications, and learning, and outlines open challenges and system qualities.

  • Problem

    Growing GPS and location-based-service use increases trajectory-data availability and demand for efficient management and analysis.

  • Method

    The survey organizes trajectory research by shared data-management components and operators, covering storage, similarity measures, search, clustering, applications, and learning.

  • Results

    The survey provides an overview of recent trajectory data management, learning, applications, and research advances across similarity search, clustering, and real-time analytics.

  • Takeaways & Limitations

    Trajectory management systems must support scalable storage, decomposed processing pipelines, and timely analysis across diverse urban applications.

  • Takeaways & Limitations

    Current trajectory-cleaning solutions require manually supplied road networks and data-dependent parameters, while no standard trajectory-data format is defined.

Abstract

from arXiv · show

Recent advances in sensor and mobile devices have enabled an unprecedented increase in the availability and collection of urban trajectory data, thus increasing the demand for more efficient ways to manage and analyze the data being produced. In this survey, we comprehensively review recent research trends in trajectory data management, ranging from trajectory pre-processing, storage, common trajectory analytic tools, such as querying spatial-only and spatial-textual trajectory data, and trajectory clustering. We also explore four closely related analytical tasks commonly used with trajectory data in interactive or real-time processing. Deep trajectory learning is also reviewed for the first time. Finally, we outline the essential qualities that a trajectory data management system should possess in order to maximize flexibility.

1 INTRODUCTION

Trajectory data has expanded through GPS, smartphones, and other proactive sensors, creating demand for systems that manage diverse urban trajectories across the full analytics pipeline. This survey organizes trajectory data management from collection and cleaning through storage, querying, clustering, applications, and deep learning.

  • Data Collection: GPS-equipped vehicles and smartphones have increased trajectory-data use in navigation and location-based services.Examples include ride-sharing and social-network check-ins.
  • Data Collection: Cameras, UAVs, and RFID can capture precise object locations proactively and continuously without battery-dependent tracking receivers.
  • Trajectory Data: A trajectory is an ordered sequence of spatial points, optionally augmented with information such as social-network or travel-blog text.The survey primarily focuses on spatial-only and spatial-textual trajectories, whose solutions and applications often overlap.
  • Survey Scope: The survey focuses primarily on urban trajectories and excludes domain-specific data such as aircraft trajectories.It distinguishes pointwise trajectory sequences from continuous moving-object projections.
  • Datasets: Human-derived data, including vehicles, is the largest source among the public trajectory datasets summarized.The cited example records 1.1 billion NYC taxi trips from January 2009 through June 2015.
  • Survey Coverage: The survey covers cleaning, storage, similarity measures, indexing, queries, urban applications, and deep trajectory learning.Its overview connects these components across the trajectory-processing pipeline.

2 MANAGEMENT SYSTEMS AND PRE-PROCESSING

This section surveys trajectory storage systems and preprocessing methods for noisy, heterogeneous urban trajectory data. It covers representations, database extensions, cleaning, compression, map-matching, and similarity-measure foundations.

  • Trajectory Representation and Storage: Traditional trajectory storage represents a trajectory as a sequence of coordinate pairs, while database systems support varying trajectory-specific capabilities.Commercial and open-source systems can be extended for trajectory management, whereas some academic systems support only one storage format or query type.
  • Trajectory Representation and Storage: Commercial systems can store and manipulate trajectories through module extensions but may incur additional cost overheads because they handle many data types.
  • Trajectory Pre-processing: GPS trajectories are noisy because devices have an average user range error of 7.8 m with 95% probability, making cleaning necessary in some processing settings.Sampling-rate variation can also affect distance and similarity computations and degrade result quality.
  • Trajectory Pre-processing: Preprocessing includes segmentation, calibration, enrichment, and compression; calibration can unify sampling strategies while correcting noisy points rather than directly filtering them.Segmentation may use spatiotemporal criteria such as location, heading, speed, curvature, sinuosity, curviness, and shape.
  • Trajectory Pre-processing: Compression reduces storage by removing points or encoding road-network segments, but simplification can reduce analytical resolution unless computation-specific error bounds are applied.Road-network compression projects trajectories onto connected segments and encodes those segments with Huffman coding.
  • Trajectory Pre-processing: Map-matching projects raw trajectories onto connected road-network paths, supporting cleaning and compression, but effectiveness depends on uncertainty, parameter selection, and ground truth.Ground truth can come from GPS-equipped vehicles, human adjudication, or simulated GPS sampling.

3 TRAJECTORY SIMILARITY MEASURES

The survey organizes trajectory similarity measures by how they compare spatial, temporal, ordered, and network-constrained trajectory representations. It contrasts their robustness, metric properties, constraints, and computational costs.

  • Pointwise Measures: Point-to-trajectory measures such as kBCT and CPD compare query points with nearby trajectory points, but they do not capture point ordering.kBCT aggregates nearest-neighbor distances, whereas CPD uses the closest pair and is described as more robust to erroneous points.
  • Taxonomy: Trajectory similarity measures are grouped into curve-based, real-distance, edit-distance, temporal-aware, and segment-based categories.The survey uses these categories to compare commonly used measures for trajectory-to-trajectory similarity.
  • Curve and Time-Series Measures: Curve- and time-series-based measures add different notions of geometric or temporal similarity, including ordering, accumulated distance, and thresholded matching.Hausdorff distance ignores ordering; DFD incorporates location and ordering; DTW sums minimum distances; LCSS and EDR use a matching threshold.
  • Edit-Distance Measures: 0 or 1 edit distances can be more robust to noisy data than DTW, but LCSS and EDR remain sensitive to their threshold τ.The cited example reports dLCSS(Q3,T5) = 4 and dEDR(Q3,T5) = 0.
  • Temporal-Aware and Segment-Based Measures: Temporal-aware pointwise methods can require sample-rate calibration, while segment-based methods reduce sample mismatch effects but may retain expensive endpoint-distance computations.Network-constrained approaches include LORS, LCRS, WED, and EBD; LORS, LCRS, and WED use dynamic programming with quadratic complexity.
  • Complexity and Robustness: Many ordering-constrained similarity measures require dynamic programming with O(n^2) time and associated space overheads, limiting efficient metric-space pruning for non-metric measures.DTW, LCSS, and EDR do not satisfy the triangle inequality; ERP is identified as the exception among the time-series measures.

4 TRAJECTORY SEARCH AND JOIN

Trajectory search spans spatial and spatial-textual queries, from region and path retrieval to nearest-neighbor and reverse-nearest-neighbor searches. Indexing decomposes trajectories into points, uses R-trees and mapping tables, and applies pruning to improve search efficiency.

  • Basic trajectory search: Range, path, and strict path queries retrieve trajectories intersecting regions, containing queried edges, or containing a queried sub-trajectory.
  • Nearest-neighbor search: Top-k trajectory search returns the most similar trajectories to a trajectory or point query using a specified similarity measure.
  • Reverse search: Reverse k-nearest-neighbor queries find trajectories for which the query object is among their k nearest neighbors, including routes relevant to bus-route capacity estimation.
  • Indexing: Trajectory indexing commonly decomposes trajectories into indexable points and uses mapping tables to recover the trajectories containing retrieved points.
  • Pruning: MBR intersection prunes range-query search spaces, while kNN methods use additional pruning techniques to reduce candidates.
  • Spatial-textual search: Spatial-textual trajectory similarity combines spatial distance with TF·IDF text similarity using a user-defined weight.

5 TRAJECTORY CLUSTERING AND CLASSIFICATION

Trajectory clustering groups similar trajectories into representative routes, while classification assigns labels to individual trajectories. Methods differ in similarity measures, parameterization, density identification, and computational demands.

  • Partition-based clustering: Partition-based clustering divides trajectories into k clusters and minimizes distances between trajectories and centroid paths.
  • Partition-based clustering: Similarity measures and parameter choices vary by application, and partition-based clustering can become computationally intractable for large collections.
  • Partition-based clustering: k-paths extends k-means to road-network trajectories, using EBD, an edge inverted index, and metric properties to reduce similarity computations.
  • Density-based clustering: Density-based methods identify dense trajectory segments and connect them into representative routes; TRACLUS clusters similar line segments after partitioning trajectories.
  • Trajectory classification: Classification assigns a label to an individual trajectory, unlike clustering, which operates over all items in a dataset.
  • Trajectory classification: Travel-purpose classification uses trajectory data to infer activity types and characterize their temporal, spatial, length, and directional patterns.

6 TRAJECTORY-BOOSTED APPLICATIONS IN URBAN PLANNING

Large-scale urban trajectory data supports real-time smart-city applications and timely decision making. The survey organizes trajectory-boosted urban applications into four broad categories.

  • Urban trajectory data is valuable for real-time smart-city applications and timely decision making, with four application categories reviewed in the survey.

6.1 Applications in Road Traffic

Road-traffic applications use trajectory data for visualization, monitoring, traffic-jam detection, and flow analysis. Mapping trajectories onto road networks both cleans data and supports real-time traffic analysis.

  • Applications in Road Traffic: Government and city trajectory data supports traffic monitoring, anomaly detection, and traffic jam and flow analysis.
  • Applications in Road Traffic: Mapping trajectories onto road networks cleans the data and enables real-time traffic jam and flow analysis.
  • Applications in Road Traffic: Visualization systems let users explore traffic conditions in specific areas or roads and potentially control traffic after inspecting movement patterns.
  • Applications in Road Traffic: Live monitoring tracks road or area usage in real time and can identify jams for commuter notifications through signs or GPS applications.
  • Applications in Road Traffic: Traffic-flow analysis discovers repeated driver movement patterns across routes without relying on domain-specific features such as speed limits.
  • Applications in Road Traffic: Anomaly detection identifies trajectories outside a predefined confidence interval and has been applied to criminal-behavior and taxi-driver-fraud detection.

6.2 Applications in Green Transport

Trajectory data supports green transport by informing network design, personalized navigation, and carpooling. The surveyed work emphasizes trip planning and common-route discovery, including demand estimation and trajectory-based matching.

  • Green transport applications use trajectory data to optimize network design, support personalized and adaptive navigation, and enable carpooling.
  • Trip planning and common-route finding are critical road-network tasks, often formulated as capacity maximization or travel-time minimization.Many such problems are NP-hard and are solved using greedy algorithms.
  • Taxi trajectories can support night-time bus-route planning by identifying potential stops through point clustering and connecting those stops into routes.
  • Historical trajectories can adapt shortest-path navigation and enrich road-network models when combined with precise map matching.
  • Ridesharing methods group passengers and drivers using historical trajectories, with the goal of keeping vehicle seats occupied.One cited carpooling system matches passengers and drivers using a trajectory-based distance similarity measure.

6.3 Applications in Tourism Planning

Trajectory data supports tourism planning through personalized trip discovery and semantic interest mining. Spatial, textual, temporal, and interactive signals are combined to identify destinations and construct preference- and time-aware tours.

  • Historical trip data can improve tourist satisfaction and help discover personalized opportunities aligned with individual preferences.The UK tourism market is projected in the cited passage to exceed £257 billion by 2025 and represent 11% of GDP.
  • Similar-trip queries can combine spatial proximity, keyword relevance, ranges, and photos to support zero-knowledge travel-route discovery.One approach used 20 million geo-tagged photos to suggest customized routes based on user preferences.
  • Enriching trajectories with text enables semantic pattern discovery that uses human interaction and descriptive information beyond spatial routes.
  • Tourism interest discovery commonly targets points of interest, regions of interest, and interactive discovery.The cited work includes spatiotemporal clustering, parameter-independent ROI definitions, and indexes for efficient ROI retrieval.
  • Semantic pattern mining seeks frequent movements satisfying spatial compactness, semantic consistency, and temporal continuity.A cited method first retrieves coarse category-based patterns and then refines them top-down.

6.4 Applications in Site Selection

Trajectory-driven site selection applies influence models to place facilities or design routes under scenario-specific constraints. The survey covers exact, bounded, greedy, and expansion-based strategies across charging, advertising, transport, and general facility-placement problems.

  • Site selection chooses facilities under a constraint while maximizing an influence-based objective over trajectory data.The formal definition uses a facility subset, constraint value, cost function, and influence model.
  • Objective functions and inputs vary by scenario, with comparisons covering constraints, map matchability, hardness reductions, acceleration strategies, and approximation guarantees.
  • The general site-selection problem is NP-hard through reduction to set cover, while approximate solutions may still scale poorly.Bounded, greedy, and expansion-based methods are described as acceleration strategies.
  • Charging-station deployment uses electric-taxi trajectories, road maps, and existing stations to reduce charging detours through placement and charging-point assignment.
  • Charging deployment can jointly maximize electric-vehicle charging revenue and minimize driver discomfort such as queueing time.
  • Billboard placement maximizes passenger influence or traffic-based exposure under a limited number of billboard locations.One cited formulation selects k trajectories to maximize expected audience influence.
  • Route-based selection includes bike-lane design under budget and connectivity constraints, using greedy network expansion to reduce connected components.
  • General facility selection can optimize probabilistic influence for k facilities, including single-location selection with k = 1 using filtering-verification.

7 EMERGING TRENDS ON DEEP TRAJECTORY LEARNING

Deep trajectory learning is reviewed across generation, recovery, representation, classification, prediction, and travel-time estimation. The surveyed methods use GANs, seq2seq models, autoencoders, RNNs, CNNs, and hybrid architectures for different trajectory analytics tasks.

  • Deep trajectory learning methods are organized into multiple categories and include emerging research trends.
  • Trajectory Data Generation: GAN-based generation produces synthetic trajectories by generating metric-space points and transforming them into sequences.Experiments reported in the cited passage show that the model captures trajectory correlations.
  • Trajectory Data Recovery: Seq2seq models recover routes between consecutive observations in low-sampling-rate trajectories.The recovery problem is studied both with road networks using map matching and without road networks.
  • Representation Learning: Fixed-dimensional trajectory representations reduce similarity-computation complexity from O(n^2) to O(n).The cited representation-learning model incorporates spatial proximity into its loss function.
  • Classification and Detection: Deep models support trajectory clustering, transportation-mode prediction, user linking, and anomalous-trajectory detection.Examples include autoencoders, LSTMs, semi-supervised RNNs, and Gaussian-mixture variational sequence autoencoders.
  • Trajectory Prediction: RNN-based prediction models learn user representations alongside spatial and temporal contexts to predict future locations.Reviewed examples model local and periodic temporal contexts, geographical context, and multimodal transitions.
  • Trajectory Prediction: CNNs can represent semantic trajectories and predict future semantic locations from matrices of semantic meanings and trajectory identifiers.
  • Travel-Time Estimation: Hybrid CNN-RNN and bidirectional LSTM models estimate path or origin-destination travel times from mobility trajectories.A cited approach uses multi-task learning for travel-time estimation, while another exploits historical trajectory-associated travel times.

8 FUTURE RESEARCH DIRECTIONS AND OPEN ISSUES

The survey identifies major gaps in end-to-end trajectory data systems and highlights emerging requirements for future trajectory sources. It calls for more automated, reproducible, integrated, and real-time-capable support.

  • Current open-source and commercial systems do not support the entire trajectory data management and analytics pipeline.
  • Data Cleaning: Automated data cleaning is needed because map matching, re-sampling, and calibration currently require manual inputs and data-dependent parameters.Manual cleaning is time-consuming and often not reproducible.
  • Trajectory Data Repositories: Public repositories of raw and cleaned trajectories, standard formats, and labeled datasets would improve reproducibility and support similarity search and classification research.The survey notes that LineString and GPX have limited use and that labeled datasets are non-existent.
  • Self-Driving Trajectory: Self-driving vehicles will generate short-term, lane-level trajectories sampled at high rates and requiring real-time response for safe driving.The cited example describes trajectories lasting five seconds.

9 CONCLUSION

The survey reviews trajectory data management, analytics, and learning by organizing problems around shared components and operators. It emphasizes broadly used similarity search and clustering techniques, real-time urban analytics, deep trajectory learning, and solution choices applicable beyond road networks.

  • The survey reviews recent progress in trajectory data management and learning, including urban applications and shared components across tasks.
  • Similarity measures, top-k similarity search, and fast clustering are widely used across trajectory problems and scenarios.
  • The survey covers four common trajectory analytics applications for real-time smart cities and reviews emerging deep trajectory learning applications.
  • Its perspectives on selecting preprocessing, storage, search, and advanced analytics solutions can apply beyond road-network domains.

A SUPPLEMENTAL FIGURES

The supplemental figures illustrate trajectory representations and urban applications, including GeoJSON LineString and GPX formats, public GPS traces, transit planning, and other urban use cases.

  • A GeoJSON Feature encodes a LineString as an ordered coordinate sequence.
  • GPX is shown as a widely used format for public GPS traces in OpenStreetMap.
  • One application uses origin-destination data and a transit network for transit network planning with commuter trajectory data.
  • The supplemental material presents four examples of urban applications for trajectory data.
Loading 2003.11547v2…