Run the LCSS Algorithm on Two Trajectories Allowing Translations

Description

A function to calculate the longest common subsequence between two trajectories. This calculation automatically uses translations to find the largest value.

Usage

1
2
LCSS(traj1, traj2, pointSpacing=-1, pointDistance=20, 
     errorMarg=2, returnTrans=FALSE)

Arguments

traj1

An m x n matrix containing trajectory1. Here m is the number of points and n is the dimension of the points.

traj2

A k x n matrix containing trajectory2. Here k is the number of points and n is the dimension of the points. The two trajectories are not required to have the same number of points.

pointSpacing

An integer value of the maximum index difference between trajectory1 and trajectory2 allowed in the calculation. A negative value sets the point spacing to unlimited.

pointDistance

A floating point number representing the maximum distance in each dimension allowed for points to be considered equivalent.

errorMarg

A floating point error margin used to scale the accuracy and speed of the calculation.

returnTrans

A boolean value to allow the best translation found to be returned as well as the LCSS value if set to true.

Details

The LCSS algorithm calculates the largest number of equivalent points between the two trajectories when traversed in a monotone way. Possible translations are calculated in each dimension and used to provide the maximum LCSS. The accuracy of the algorithm can be varied to provide faster or slower calculations. Please see the references for more information.

Value

An integer value is returned. This represents the maximum LCSS value obtained using the variables provided. If returnTrans is set to TRUE, then the LCSS value and the translations are returned as a vector. The first value of this vector is the LCSS value and the translations follow directly afterwards. If a problem occurs, then a string containing information about the problem is returned.

Author(s)

Kevin Toohey

References

Vlachos, M., Kollios, G. and Gunopulos, D. (2002) Discovering similar multidimensional trajectories. Paper presented at the Data Engineering, 2002. Proceedings. 18th International Conference on.

See Also

LCSSCalc, LCSSRatio, LCSSRatioCalc, LCSSTranslation

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Creating two trajectories.
path1 <- matrix(c(0, 1, 2, 3, 0, 1, 2, 3), 4)
path2 <- matrix(c(0, 1, 2, 3, 4, 5, 6, 7), 4)

# Running the LCSS algorithm on the trajectories.
LCSS(path1, path2, 2, 2, 0.5)

# Running the LCSS algorithm on the trajectories
# and returning the translation as well.
LCSS(path1, path2, 2, 2, 0.5, TRUE)