** OWD(One Way Distance)**算法也是一种描述两个路径之间相似度的方法,最早大概提出于06年左右。最朴素的OWD算法的思路也非常简单,就是把路径之间的距离转化为点到路径的距离再加以处理。这里只对这种算法做简要介绍,至于深层次的理论有空再研究论文。
在定义路径间的距离D_{owd}之前,我们先定义点到路径的距离D_{point}:
对于点p和一个由多个点组成的路径T,定义他们之间的距离为
其中D_{Euclid}(p,q)表示p.q之间的欧式距离。
然后,我们定义路径T_1到路径T_2的单向距离D_{owd}(T_1,T_2)为:
(对于非离散的路径,我们可以把他看成是一个积分过程)
很容易看出来,这个单向距离不具有对称性,即D_{owd}(T_1,T_2)与D_{owd}(T_2,T_1)不一定相等。那么为了得到一个对称的结果,我们定义一个新的度量标准:
这就是OWD距离中最终用来判定路径相似度的标准。
从OWD距离计算的方式就可以看出,他能够很好的对不同长度的路径间距离进行归一化,而且对于噪声敏感度比较低。
Bin Lin, Jianwen Su, One Way Distance: For Shape Based Similarity Search of Moving Object Trajectories. In Geoinformatica (2008)