Home

Awesome

trajectory_distance

=====================

trajectory_distance is a Python module for computing distances between 2D-trajectory objects. It is implemented in Cython.

Description

9 distances between trajectories are available in the trajectory_distance package.

  1. SSPD (Symmetric Segment-Path Distance) [1]
  2. OWD (One-Way Distance) [2]
  3. Hausdorff [3]
  4. Frechet [4]
  5. Discret Frechet [5]
  6. DTW (Dynamic Time Warping) [6]
  7. LCSS (Longuest Common Subsequence) [7]
  8. ERP (Edit distance with Real Penalty) [8]
  9. EDR (Edit Distance on Real sequence) [9]

Dependencies

trajectory_distance is tested to work under Python 3.6 and the following dependencies:

Install

This package can be build using distutils.

Move to the package directory and run :

python setup.py install 

to build Cython files. Then run:

pip install .

to install the package into your environment.

How to use it

You only need to import the distance module.

import traj_dist.distance as tdist

All distances are in this module. There are also two extra functions 'cdist', and 'pdist' to compute pairwise distances between all trajectories in a list or two lists.

Trajectory should be represented as nx2 numpy array. See traj_dist/example.py file for a small working exemple.

Some distance requires extra-parameters. See the help function for more information about how to use each distance.

Performance

The time required to compute pairwise distance between 100 trajectories (4950 distances), composed from 3 to 20 points (data/benchmark.csv) :

EuclidanSpherical
discret frechet0.0659620761871-1.0
dtw0.07815694808960.114996194839
edr0.06952214241030.106939792633
erp0.1717379093170.319380998611
frechet29.1885719299-1.0
hausdorff0.3101999759670.780081987381
lcss0.07119512557980.111418008804
sowd grid, precision 50.1647810935970.159924983978
sowd grid, precision 60.9737920761110.954225063324
sowd grid, precision 77.625744104397.78553795815
sspd0.3141188621520.807314872742

See traj_dist/benchmark.py to generate this benchmark on your computer.

References

  1. P. Besse, B. Guillouet, J.-M. Loubes, and R. Francois, “Review and perspective for distance based trajectory clustering,” arXiv preprint arXiv:1508.04904, 2015.
  2. B. Lin and J. Su, “Shapes based trajectory queries for moving objects,” in Proceedings of the 13th annual ACM international workshop on Geographic information systems . ACM, 2005, pp. 21–30.
  3. F. Hausdorff, “Grundz uge der mengenlehre,” 1914
  4. H. Alt and M. Godau, “Computing the frechet distance between two polygonal curves,” International Journal of Computational Geometry & Applications , vol. 5, no. 01n02, pp. 75–91, 1995.
  5. T. Eiter and H. Mannila, “Computing discrete fr ́ echet distance,” Citeseer, Tech. Rep., 1994.
  6. D. J. Berndt and J. Clifford , “Using dynamic time warping to find patterns in time series.” in KDD workshop, vol. 10, no. 16. Seattle, WA, 1994, pp. 359–370
  7. M. Vlachos, G. Kollios, and D. Gunopulos, “Discovering similar multi- dimensional trajectories,” in Data Engineering, 2002. Proceedings. 18th International Conference on .IEEE, 2002, pp. 673–684
  8. L. Chen and R. Ng, “On the marriage of lp-norms and edit distance,” in Proceedings of the Thirtieth international conference on Very large data bases-Volume 30 . VLDB Endowment, 2004, pp. 792–803.
  9. L. Chen, M. T. ̈ Ozsu, and V. Oria, “Robust and fast similarity search for moving object trajectories,” in Proceedings of the 2005 ACM SIGMOD international conference on Management of data . ACM, 2005, pp. 491–502.