traj-dist-rs

High-performance trajectory distance & similarity measures in Rust and Python.

A high-performance Rust implementation of trajectory distance algorithms with Python bindings, offering significant speed improvements over the original traj-dist library.

About

traj-dist-rs is a high-performance trajectory distance calculation library written in Rust, providing both native Rust APIs and Python bindings via PyO3. It is based on the original traj-dist library with additional algorithms (e.g., EDwP), focusing on performance optimization and modern language features.

Why traj-dist-rs?

Performance: ~220x faster than traj-dist's Python implementation and ~6.5x faster than Cython implementation on average
Batch Computation: Native pdist and cdist functions with parallel support up to 130x faster than traj-dist
Zero Dependencies: Only requires numpy >= 1.21 - no heavy dependencies like polars, pyarrow, pandas, or shapely
Safety: Rust's memory safety guarantees eliminate common runtime errors
Cross-platform: Supports Linux, macOS, and Windows with native binaries
Dual API: Use it from Python or Rust with minimal overhead
Accuracy: All algorithms verified against original implementation with < 1.5e-8 error margin

Performance Overview

traj-dist-rs benchmark speedup

Median benchmark summary:

~231x faster than traj-dist (Python) on average
~15.3x faster than traj-dist (Cython) on average
Parallel batch pdist / cdist reaches up to ~61.1x speedup on large inputs

See performance.md for the full benchmark report and additional plots.

Features

Supported Distance Algorithms

Algorithm	Full Name	Best For
SSPD	Symmetric Segment-Path Distance	General similarity, noise tolerance
DTW	Dynamic Time Warping	Similarity with time warping, flexible alignment
Frechet	Fréchet Distance (Continuous)	Exact geometric similarity, considers all curve points
Discret Frechet	Discrete Fréchet Distance	Geometric similarity, path-based matching
Hausdorff	Hausdorff Distance	Maximum distance, outlier-sensitive similarity
LCSS	Longest Common Subsequence	Robust similarity with noise tolerance
EDR	Edit Distance on Real sequence	Similarity with noise and outlier tolerance
ERP	Edit distance with Real Penalty	Robust similarity with gap handling
EDwP	Edit Distance with Projections	Inconsistent sampling rates, projection-based matching

Distance Types

Euclidean - 2D Euclidean distance (all algorithms)
Spherical - Haversine distance for geographic coordinates (all algorithms except Frechet, Discret Frechet, and EDwP)

Batch Computation

pdist - Pairwise distance matrix for trajectory collections (compressed format)
cdist - Cross-distance matrix between two trajectory collections
Parallel processing - Automatic parallelization using Rayon for large datasets
Progress display - Built-in progress bar via show_progress=True (powered by indicatif, rendered to stderr)
Metric API - Type-safe configuration with factory methods

Additional Features

Matrix return for DP-based algorithms (DTW, LCSS, EDR, ERP, Discret Frechet, EDwP)
Precomputed distance matrix support for efficient batch computations
Zero-copy NumPy array support for optimal performance
Pickle serialization for DpResult objects (compatible with joblib)
Comprehensive error handling for invalid inputs
Full Python type hints for better IDE support

Keywords / Search Terms

Common search terms related to this library:

Core concepts: trajectory similarity, trajectory distance, similarity measures, trajectory analysis
Algorithms: DTW, LCSS, EDR, ERP, Fréchet distance, Hausdorff distance, SSPD
Applications: trajectory clustering, trajectory similarity search, nearest neighbor retrieval, mobility data analysis, GPS trace analysis
Domains: time series similarity, spatiotemporal data, movement pattern mining, anomaly detection

Migration from traj-dist

If you used the original traj-dist library for trajectory similarity measurement, this library is compatible and offers significant performance improvements:

Algorithm compatibility: Core algorithms (SSPD, DTW, Hausdorff, LCSS, EDR, ERP, Frechet, Discret Frechet) supported, plus EDwP (not in original traj-dist)
Performance: 3-10x faster than Cython implementation

Quick Start

Python

import numpy as np
import traj_dist_rs

# Define trajectories as list of [x, y] coordinates or numpy arrays
traj1 = [[0.0, 0.0], [1.0, 1.0], [2.0, 2.0]]
traj2 = [[0.1, 0.1], [1.1, 1.1], [2.1, 2.1]]

# Calculate SSPD distance
distance = traj_dist_rs.sspd(traj1, traj2, dist_type="euclidean")
print(f"SSPD distance: {distance}")

# Calculate DTW distance (returns DpResult with distance and optional matrix)
result = traj_dist_rs.dtw(traj1, traj2, dist_type="euclidean", use_full_matrix=False)
print(f"DTW distance: {result.distance}")

# Calculate Hausdorff distance
distance = traj_dist_rs.hausdorff(traj1, traj2, dist_type="spherical")
print(f"Hausdorff distance: {distance}")

# Batch computation with pdist (pairwise distances)
trajectories = [np.array([[0.0, 0.0], [1.0, 1.0]]) for _ in range(10)]
metric = traj_dist_rs.Metric.sspd(type_d="euclidean")
distances = traj_dist_rs.pdist(trajectories, metric=metric, parallel=True)
print(f"Computed {len(distances)} pairwise distances")

# With progress bar (rendered to stderr)
distances = traj_dist_rs.pdist(trajectories, metric=metric, parallel=True, show_progress=True)

# Cross-distance computation with cdist
dist_matrix = traj_dist_rs.cdist(trajectories[:5], trajectories[5:], metric=metric)
print(f"Distance matrix shape: {dist_matrix.shape}")

Rust

use traj_dist_rs::distance::sspd::sspd;
use traj_dist_rs::distance::dtw::dtw;
use traj_dist_rs::distance::base::TrajectoryCalculator;
use traj_dist_rs::distance::distance_type::DistanceType;
use traj_dist_rs::distance::batch::{pdist, Metric, DistanceAlgorithm};

fn main() {
    let traj1 = vec![[0.0, 0.0], [1.0, 1.0], [2.0, 2.0]];
    let traj2 = vec![[0.1, 0.1], [1.1, 1.1], [2.1, 2.1]];

    // Calculate SSPD distance
    let dist = sspd(&traj1, &traj2, DistanceType::Euclidean);
    println!("SSPD distance: {}", dist);

    // Calculate DTW distance
    let calculator = TrajectoryCalculator::new(&traj1, &traj2, DistanceType::Euclidean);
    let result = dtw(&calculator, false);
    println!("DTW distance: {}", result.distance);

    // Batch computation with pdist
    let trajectories = vec![
        vec![[0.0, 0.0], [1.0, 1.0]],
        vec![[0.0, 1.0], [1.0, 0.0]],
        vec![[0.5, 0.5], [1.5, 1.5]],
    ];
    let metric = Metric::new(DistanceAlgorithm::SSPD, DistanceType::Euclidean);
    let distances = pdist(&trajectories, &metric, true, true).unwrap();
    println!("Computed {} pairwise distances", distances.len());
}

Installation

From PyPI (Python)

pip install traj-dist-rs

Minimal Dependencies: traj-dist-rs only requires numpy >= 1.21 to function. This makes it extremely lightweight and easy to install compared to alternatives that depend on pandas, shapely, or other heavy libraries.

Requirements

Python: 3.10, 3.11, 3.12, or 3.13
NumPy: >= 1.21 (the only runtime dependency)
Platform: Linux, macOS, or Windows

From crates.io (Python)

cargo add traj-dist-rs --features parallel

Installation Options

Basic Installation (minimal dependencies):

pip install traj-dist-rs

Installation with Test Dependencies (for development):

pip install traj-dist-rs[test]

From Source (requires Rust toolchain):

Prerequisites:

Rust 1.85 or later
uv

Build and install:

# Clone the repository
git clone https://github.com/Davidham3/traj-dist-rs.git
cd traj-dist-rs

# Compile and install via uv
uv pip install .

Rust-only build:

cargo build --release --features parallel

Performance

Compared to the original traj-dist implementation (based on median values from K=1000 trajectory pairs):

Overall Performance

Implementation	Average Speedup
Rust vs Python	~220x faster
Rust vs Cython	~6.5x faster

By Distance Type

Euclidean Distance:

Rust vs Python: ~329x faster (range: 169x - 517x)
Rust vs Cython: ~8.9x faster (range: 6.3x - 12.9x)

Spherical Distance:

Rust vs Python: ~93x faster (range: 47x - 195x)
Rust vs Cython: ~3.6x faster (range: 2.3x - 6.8x)

Batch Computation Performance

pdist (DTW, 5 trajectories, varying lengths):

Trajectory Length	Rust Seq vs `traj-dist`	Rust Par vs `traj-dist`
10 points	9.15x	0.21x (parallel overhead)
100 points	11.58x	9.73x
1000 points	12.47x	71.24x

cdist (DTW, 5×5, varying lengths):

Trajectory Length	Rust Seq vs `traj-dist`	Rust Par vs `traj-dist`
10 points	10.77x	0.55x (parallel overhead)
100 points	14.45x	34.81x
1000 points	12.27x	50.36x

Real-world Example: TrajCL Data Preprocessing

Dataset: 7,000 trajectories (Porto dataset)
Task: DTW distance matrix computation
Performance: 31.8x faster than traj-dist baseline (2933s → 92s)

For detailed performance analysis with statistics, see performance.md.

Documentation

Installation Guide: installation.md
Python User Guide: usage_for_python.ipynb
Rust User Guide: usage_for_rust.ipynb
Performance Report: performance.md
Examples: examples/ - Python and Rust example code

Testing

Run comprehensive integration tests:

bash scripts/pre_build.sh

Contributing

We welcome contributions! Please see our contributing guidelines:

Fork the repository
Create a feature branch (git checkout -b feature/amazing-feature)
Make your changes
Run tests and ensure they pass via bash scripts/pre_build.sh
Commit your changes (git commit -m 'Add amazing feature')
Push to the branch (git push origin feature/amazing-feature)
Open a Pull Request

Development Workflow

For daily development, use the pre-build script:

bash scripts/pre_build.sh

This script will:

Format Rust and Python code
Run linting (clippy, ruff)
Run all tests (Rust + Python)
Generate Python stub files
Build Python bindings

Project Structure

traj-dist-rs/
├── src/
│   ├── distance/       # Distance algorithm implementations
│   ├── binding/        # Python bindings (PyO3)
│   └── lib.rs          # Library entry point
├── tests/              # Rust integration tests
├── py_tests/           # Python integration tests
├── python/             # Python package source
├── docs/               # Documentation
└── scripts/            # Build and utility scripts

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

Original traj-dist library for algorithm reference
PyO3 for Python bindings
The Rust community for excellent tooling and libraries

Support

Issues: Report bugs and request features via GitHub Issues
Discussions: Join discussions about usage and development
Documentation: Check the docs directory for detailed guides

traj-dist-rs 1.0.0-rc.5