PaperlayerView exact revision on arXiv

Source-linked AI summary

Contrastive Trajectory Similarity Learning with Dual-Feature Attention

Yanchuan Chang, Jianzhong Qi, Yuxuan Liang, Egemen Tanin

arXiv:2210.05155v3cs.DBcs.LG

TL;DR

Trajectory similarity measures affect database query results and efficiency, but existing measures face effectiveness and speed challenges. TrajCL combines contrastive learning with augmentations and a dual-feature attention encoder. Across four datasets, it improves similarity measurement and heuristic-measure estimation against state-of-the-art methods.

  • Problem

    Trajectory similarity determines query results and efficiency, while existing measures face effectiveness and speed challenges.

    Source: §I · p. 1

  • Method

    TrajCL uses contrastive learning with trajectory augmentations and a dual-feature attention encoder for structural and spatial features.

    Source: §I · p. 2

  • Results

    Across four datasets, TrajCL improved measuring accuracy by 3.22 times and reduced running time by more than 50% on average; heuristic-measure prediction accuracy improved by up to 56%.

    Source: §I · p. 2

  • Takeaways & Limitations

    Experiments on four real trajectory datasets show significant improvements over state-of-the-art methods in measuring similarity and approximating heuristic measures.

    Source: §VI · pp. 13–14

Abstract

from arXiv · show

Trajectory similarity measures act as query predicates in trajectory databases, making them the key player in determining the query results. They also have a heavy impact on the query efficiency. An ideal measure should have the capability to accurately evaluate the similarity between any two trajectories in a very short amount of time. Towards this aim, we propose a contrastive learning-based trajectory modeling method named TrajCL. We present four trajectory augmentation methods and a novel dual-feature self-attention-based trajectory backbone encoder. The resultant model can jointly learn both the spatial and the structural patterns of trajectories. Our model does not involve any recurrent structures and thus has a high efficiency. Besides, our pre-trained backbone encoder can be fine-tuned towards other computationally expensive measures with minimal supervision data. Experimental results show that TrajCL is consistently and significantly more accurate than the state-of-the-art trajectory similarity measures. After fine-tuning, i.e., to serve as an estimator for heuristic measures, TrajCL can even outperform the state-of-the-art supervised method by up to 56% in the accuracy for processing trajectory similarity queries.

I. INTRODUCTION

Trajectory similarity determines both database query results and efficiency, yet existing measures face accuracy and speed challenges. TrajCL combines contrastive learning, trajectory augmentations, and dual-feature attention to address them.

I. INTRODUCTION

  • Trajectory similarity is a query predicate that affects both which results trajectory databases return and query efficiency.Unlike numeric and character data, trajectories lack many universally applicable comparison criteria.Source: §I · p. 1
  • Heuristic measures use hand-crafted point matching, while learned measures compare trajectory embeddings; both can struggle with low-quality data, long spatial correlations, or speed.Heuristic methods can require quadratic time in trajectory length, while recurrent learned encoders limit parallel computation.Source: §I · p. 1, §II · pp. 2–3

II. RELATED WORK

  • TrajCL uses four trajectory augmentations and adaptive attention over structural and spatial features, while related trajectory encoders use recurrent, convolutional, image-based, or vanilla-attention designs.The paper positions this dual-feature encoder as addressing effectiveness and efficiency limitations of existing learned measures.Source: §I · p. 2, §II · p. 3

I. INTRODUCTION

  • TrajCL improved measuring accuracy by 3.22 times and reduced running time by more than 50% on average; heuristic-measure prediction accuracy rose by up to 56%.These results compare TrajCL with state-of-the-art learned measures and supervised methods, respectively.Source: §I · p. 2

III. SOLUTION OVERVIEW

TrajCL creates two augmented views of each trajectory, encodes their structural and spatial features, and trains the representations contrastively. The trained encoder can compare trajectories directly or support heuristic-measure approximation.

III. SOLUTION OVERVIEW

  • After training, average-pooled trajectory representations can be compared directly, with trajectory similarity represented by the L1 distance between embeddings.The encoder can also be connected to other models to approximate heuristic similarity measures.Source: §III · pp. 3–4
  • Two trajectory views are generated directly from each input without manual labels, then enriched into pointwise structural and spatial feature embeddings.The views pass through backbone encoders and projection heads for contrastive training.Source: §III · p. 3
  • The dual-branch model trains on positive view pairs and negative embeddings from current and recent batches, using InfoNCE to maximize positive agreement and minimize negative agreement.A fixed-size queue stores recent negative samples, while momentum updates keep their encoder and projection parameters changing smoothly.Source: §III · p. 3

IV. MODEL DETAILS

TrajCL introduces four trajectory augmentations to create varied views for contrastive learning. They perturb locations, remove points, truncate trajectories, or simplify their shape, with parameters controlling how far variants depart from the input.

A. Trajectory Augmentation

  • The four proposed augmentations are point shifting, point masking, trajectory truncating, and trajectory simplification, designed to cover common trajectory transformations.The input is shown in dark blue and generated variants in light blue in the examples.Source: A. Trajectory Augmentation · p. 4, Figure 3 · p. 4
  • Point shifting adds random coordinate offsets to learn similarity despite minor location differences; the experiments bound offsets at 100 meters.The offsets use a bounded Gaussian distribution because GPS location errors cannot be arbitrarily large.Source: A. Trajectory Augmentation · p. 4
  • Point masking removes a random subset of points to model trajectories with varying sampling rates or incomplete records; experiments mask 30% of points.The masking probability is independently and uniformly distributed across points.Source: A. Trajectory Augmentation · p. 4
  • Trajectory truncating cuts a prefix, suffix, or both to expose partially overlapping trajectories, such as those relevant to carpooling.The experiments keep 70% of the points in a truncated variant.Source: A. Trajectory Augmentation · p. 4
  • Trajectory simplification removes points that are not critical to overall shape, using Douglas–Peucker to retain critical points such as turns.The experiments use a 100-meter threshold for deciding when breaking points are sufficiently close to line segments.Source: A. Trajectory Augmentation · pp. 4–5

B. Pointwise Trajectory Feature Enrichment

TrajCL enriches each trajectory point with structural and spatial embeddings, then adds positional information to both. The two feature types represent trajectory shape and connectivity, as well as fine-grained location characteristics.

B. Pointwise Trajectory Feature Enrichment

  • Each point receives structural and spatial embeddings, with positional encoding added to preserve its relative sequence position.The passages describe structural and spatial features as complementary coarse-grained and fine-grained location information.Source: B. Pointwise Trajectory Feature… · p. 5
  • Structural features encode trajectory shape and point connectivity by mapping points to grid cells and learning embeddings from an eight-neighbor cell graph.The cell embeddings are learned with node2vec and used to represent the trajectory points.Source: B. Pointwise Trajectory Feature… · p. 5
  • Spatial features represent each point with its coordinates, the angle between adjacent segments, and their mean length.The spatial feature tuple is (x_i, y_i, r_i, l_i).Source: B. Pointwise Trajectory Feature… · p. 5
  • Sine and cosine position values are added to both feature embeddings to encode each point’s sequence index.The passages state that e_i,j encodes position i and is added to the structural and spatial embeddings.Source: B. Pointwise Trajectory Feature… · p. 5

C. Dual-Feature Self-Attention-Based Backbone Encoder

DualSTB encodes structural and spatial trajectory features with DualMSM, which models their attentions separately and integrates them adaptively. The resulting point representations pass through stacked encoder layers and are averaged into a trajectory embedding.

C. Dual-Feature Self-Attention-Based Backbone Encoder

  • DualMSM processes structural and spatial features separately while also modeling their joint impact to produce trajectory representations.It takes both feature types as inputs and outputs hidden representations of trajectory points.Source: C. Dual-Feature Self-Attention-Based… · pp. 5–6
  • DualSTB follows a multi-layer Transformer encoder structure, applying residual connections, layer normalization, and an MLP after DualMSM.The experiments stack two layers, then average the final point representations along each dimension to obtain the trajectory representation.Source: C. Dual-Feature Self-Attention-Based… · p. 6
  • DualMSM learns separate attention coefficients for each feature type, then adaptively combines their correlations using a learnable weighting parameter.The paper contrasts this with vanilla MSM, which accepts one input feature type and does not support this separate-then-adaptive integration.Source: C. Dual-Feature Self-Attention-Based… · p. 6
  • Concatenating structural and spatial features into one MSM input is reported as empirically inferior to DualMSM’s separate attention and adaptive integration.The paper identifies this as one of the differences between DualMSM and vanilla MSM.Source: C. Dual-Feature Self-Attention-Based… · p. 6

D. Cost Analysis

The cost analysis gives TrajCL’s trajectory-encoding complexity, compares it with representative alternatives, and separates embedding computation from pairwise similarity calculation.

D. Cost Analysis

  • TrajCL computes a trajectory embedding in O(l^2 · d · L) time, where l is the point count and L is the number of DualMSM layers.The stated cost excludes O(l) pointwise feature construction because trajectory encoding dominates.Source: D. Cost Analysis · p. 7
  • t2vec and E2DTC use O(l · d^2 · L), TrjSR uses O(m^2 · k^2 · n_k · c_l · L), and CSTRM matches TrajCL’s stated complexity.The passage defines m, k, n_k, and c_l as TrjSR’s image, kernel, kernel-count, and channel dimensions.Source: D. Cost Analysis · p. 7
  • After embeddings are computed, comparing two trajectories takes time linear in the embedding dimension d.Source: D. Cost Analysis · p. 7

V. EXPERIMENTS

Experiments on four real-world trajectory datasets compare TrajCL with heuristic and learned measures. TrajCL ranks similar trajectories more accurately across database sizes and trajectory modifications, and also performs well when tested across datasets.

A. Experimental Settings

  • The evaluation used Porto, Chengdu, Xi’an, and Germany datasets, filtered to trajectories with 20–200 points, and compared heuristic and learned measures.The section also describes downstream experiments fine-tuning TrajCL to approximate heuristic measures.Source: §V · p. 7, A. Experimental Settings · p. 7

B. Learning Trajectory Similarity

  • On Porto at |D|=100K, TrajCL’s mean rank was 1.010 versus 6.376 for Hausdorff and 3.068 for t2vec, outperforming all competitors across four datasets.TrajCL’s worst mean rank was 1.200 on Chengdu; the best baseline, TrjSR, reached 17.873 there.Source: Table III · p. 8, B. Learning Trajectory Similarity · p. 8
  • With down-sampling, TrajCL again achieved the smallest mean ranks, reducing Porto mean rank by at least 0.87 times versus EDwP and 2.17 times versus t2vec.Its advantage reached 11.38 times versus EDwP and 12.01 times versus t2vec.Source: B. Learning Trajectory Similarity · p. 8, Table IV · p. 9
  • Under point distortion, TrajCL outperformed all competitors, reducing mean rank versus t2vec by up to 2.85, 16.43, 27.37, and 3.67 times across Porto, Chengdu, Xi’an, and Germany.The authors note that random distortion can change relative similarities in either direction, so mean ranks may fluctuate as distortion rates vary.Source: B. Learning Trajectory Similarity · pp. 8–9, Table V · p. 9
  • When trained on Porto and tested on Xi’an, TrajCL outperformed t2vec and most dataset-independent heuristics; EDwP was the exception, with mean ranks of 4.211 versus 3.606.The authors attribute cross-dataset generalizability to the dual-feature encoder’s ability to capture generic correlation patterns between similar trajectories.Source: Table VI · p. 9, B. Learning Trajectory Similarity · p. 9

C. Efficiency of Similarity Computation

TrajCL’s similarity computation is fast, particularly on GPU, while its training time is competitive with the learned baselines. Its relative speed depends on hardware and on the trajectory lengths that affect heuristic methods.

C. Efficiency of Similarity Computation

  • TrajCL was slightly slower to train than CSTRM on Porto, Chengdu, and Xi’an, but was fastest on Germany at under 9 minutes.CSTRM triggered an out-of-memory error on Germany; its training set had 30,000 trajectories, compared with 200,000 for each other dataset.Source: Table VII · p. 9, C. Efficiency of Similarity Computation · p. 10
  • On GPU, TrajCL completed 10^8 similarity computations in less than 20 seconds, or 0.2 µs per computation, and was up to 104 times faster than heuristic methods.On CPU, it was 4.26 times faster than Hausdorff on Porto and up to 103 times faster than EDwP on Xi’an.Source: Table VIII · p. 10, C. Efficiency of Similarity Computation · p. 10
  • On CPU, t2vec and E2DTC were faster than TrajCL, whereas on GPU TrajCL was faster; the authors relate this difference to recurrent computation versus TrajCL’s single-step computation.Heuristic running times varied more across datasets because they are affected by trajectory length.Source: C. Efficiency of Similarity Computation · p. 10

D. Training Scalability

TrajCL reaches satisfactory performance after a short training run, and training benefits from more trajectories, with diminishing gains beyond 50,000 original trajectories.

D. Training Scalability

  • By the 7th epoch, after about 20 minutes, TrajCL had achieved satisfactory performance, with lower mean ranks as training continued.The learning curve is shown in Fig. 5a.Source: Figure 5 · p. 10, D. Training Scalability · p. 10
  • Performance gains diminished beyond 50,000 original training trajectories; training on 50,000 took about 15 minutes.The default training set remained 200,000 because baseline methods required at least that many trajectories.Source: Figure 5 · p. 10, D. Training Scalability · p. 10

E. Efficiency of K Nearest Neighbor Queries

The kNN experiment tests learned trajectory embeddings with an existing vector index, rather than proposing a new trajectory index. TrajCL’s queries were substantially faster than Hausdorff’s, with lower memory use at index construction but longer build time.

E. Efficiency of K Nearest Neighbor Queries

  • The experiment indexed TrajCL embeddings with Faiss to assess query efficiency using an existing kNN algorithm, not to introduce a new trajectory index.The authors describe this as the first reported non-full-scan kNN results over trajectories based on learned embeddings.Source: E. Efficiency of K Nearest Neighbor… · p. 10
  • At 1 million trajectories, the TrajCL (Faiss) index used 2.9 GB versus 30.8 GB for the Hausdorff (DFT) index, but took about twice as long to build.The added TrajCL construction time was spent converting trajectories to embeddings; DFT stores auxiliary data for query pruning.Source: Table IX · p. 11, E. Efficiency of K Nearest Neighbor… · p. 11
  • Across databases of 0.1, 1, and 10 million trajectories, TrajCL’s kNN queries were about two orders of magnitude faster than Hausdorff; the Hausdorff index ran out of memory at 10 million.The comparison used 1,000 queries over databases constructed from distorted Xi’an trajectories.Source: E. Efficiency of K Nearest Neighbor… · pp. 10–11, Figure 6 · p. 11

F. Approximating Heuristic Measures

Fine-tuned TrajCL approximates heuristic measures with very few labels, while ablations examine its encoder components and trajectory augmentations.

F. Approximating Heuristic Measures

G. Ablation Study

  • Without fine-tuning, TrajCL beats both component variants in mean rank; with fine-tuning, it remains better overall except when approximating EDwP.Source: G. Ablation Study · pp. 11–12, Figure 7 · p. 12
  • Masking targets nonadjacent-point correlations for varying sampling rates, truncation links partial to full trajectories, shifting overlaps with grid-cell noise handling, and simplification may drop key patterns.Source: G. Ablation Study · p. 12
  • TrajCL is not heavily affected by masking and truncation parameters except at extremes; defaults of ρd=0.3 and ρb=0.7 reach the lowest mean rank with HR@5 near its best.Source: G. Ablation Study · pp. 12–13, Figure 9 · p. 13
  • Point masking and trajectory truncating yield the best overall similarity-learning results and are the defaults; using the same augmentation for both views may be suboptimal.Source: G. Ablation Study · p. 12, Figure 8 · p. 13

H. Parameter Study

TrajCL improves trajectory-similarity accuracy across four real datasets. Parameter studies identify settings that balance predictive performance with training and inference cost.

H. Parameter Study

  • Without fine-tuning, TrajCL performs better overall when embedding dimensionality d is at most 256; larger d can improve heuristic approximation after fine-tuning but increases fine-tuning and inference time.The paper uses d=256 by default to balance accuracy and efficiency.Source: H. Parameter Study · p. 13, Figure 10 · p. 13
  • Performance improves as encoder layers increase, then drops beyond four layers; more layers also cost substantially more to train and run, so the default encoder has two layers.Source: H. Parameter Study · p. 13, Figure 11 · p. 13
  • Increasing the negative-sample queue generally lowers mean rank and raises HR@5, while increasing training cost; the default queue size is 2,048.Source: H. Parameter Study · p. 13, Figure 12 · p. 13

VI. CONCLUSION

  • Across four real trajectory datasets, TrajCL significantly improves accuracy for similarity measurement and heuristic-measure approximation versus state-of-the-art methods.Source: §VI · pp. 13–14

Related papers

Loading 2210.05155v3…