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.

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

All distances but Discret Frechet and Discret Frechet are are available with Euclidean or Spherical option :
Euclidean is based on Euclidean distance between 2D-coordinates.
Spherical is based on Haversine distance between 2D-coordinates.
Grid representation are used to compute the OWD distance.
Python implementation is also available in this depository but are not used within traj_dist.distance module.

Dependencies

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

NumPy >= 1.14.0
Cython >= 0.27.3
shapely >= 1.6.4
Geohash ==1.0
pandas >= 0.20.3
scipy >=0.19.1
A working C/C++ compiler.

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) :

	Euclidan	Spherical
discret frechet	0.0659620761871	-1.0
dtw	0.0781569480896	0.114996194839
edr	0.0695221424103	0.106939792633
erp	0.171737909317	0.319380998611
frechet	29.1885719299	-1.0
hausdorff	0.310199975967	0.780081987381
lcss	0.0711951255798	0.111418008804
sowd grid, precision 5	0.164781093597	0.159924983978
sowd grid, precision 6	0.973792076111	0.954225063324
sowd grid, precision 7	7.62574410439	7.78553795815
sspd	0.314118862152	0.807314872742

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

References

P. Besse, B. Guillouet, J.-M. Loubes, and R. Francois, “Review and perspective for distance based trajectory clustering,” arXiv preprint arXiv:1508.04904, 2015.
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.
F. Hausdorff, “Grundz uge der mengenlehre,” 1914
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.
T. Eiter and H. Mannila, “Computing discrete fr ́ echet distance,” Citeseer, Tech. Rep., 1994.
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
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
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.
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.