Signature-Based Trajectory Similarity Join
Signature-Based Trajectory Similarity Join
复制标题
基于签名的轨迹相似性连接
DOI：
10.1109/tkde.2017.2651821
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Jianhua Feng
中科院分区：
文献类型：
--
作者：
Na Ta;Guoliang Li;Jianhua Feng
新出现的车辆轨迹数据为许多现实世界的应用提供了机会，例如基于频繁轨迹的导航系统、道路规划、拼车等。相似性连接是实现这些应用的关键操作，它从两个大的轨迹集合中找到相似/相似的轨迹对。现有的轨迹相似性度量依赖于对齐两个轨迹的采样点。然而，由于采样率不同或车速不同，类似轨迹上的采样点可能不会对齐。为了解决这一问题，我们提出了一种新的双向映射相似度(<；内联公式<；Tex-Math notation=“LaTeX”>；$\mathtt{BDS}$<；/tex-math>；<；alternatives>；<；内联-图形xlink:href=“li-ieq1-2651821.gif”/>；<；/alternatives>；<；/inline-formula>；)，这允许轨迹的采样点与另一轨迹上的最近位置(可能不是采样点)对齐，反之亦然。针对每两条轨迹的枚举和相似度计算代价较高的问题，本文提出了一种基于签名的轨迹相似性连接框架<；MonSpace&>//MonSpace&>。<；monospace>；Strain-Join<；/monospace>；首先为每个轨迹生成签名，以便如果两个轨迹不共享公共签名，则它们不可能相似。为了利用这一性质来剪枝相异对，我们设计了几种生成高质量签名的技术，并提出了一种高效的过滤算法来剪枝相异对。对于没有被过滤算法剪枝的对，我们提出了有效的验证算法来验证它们是否相似。在真实数据集上的实验结果表明，我们的算法在有效性和效率方面都优于最先进的技术。
Emerging vehicular trajectory data have opened up opportunities to benefit many real-world applications, e.g., frequent trajectory based navigation systems, road planning, car pooling, etc. The similarity join is a key operation to enable such applications, which finds <italic>similar</italic> trajectory pairs from two large collections of trajectories. Existing similarity metrics on trajectories rely on aligning sampling points of two trajectories. However, due to different sampling rates or different vehicular speeds, the sample points in similar trajectories may not be aligned. To address this problem, we propose a new bi-directional mapping similarity (<inline-formula> <tex-math notation="LaTeX">$\mathtt{BDS}$</tex-math><alternatives> <inline-graphic xlink:href="li-ieq1-2651821.gif"/></alternatives></inline-formula>), which allows a sample point of a trajectory to align to the closest location (which may not be a sample point) on the other trajectory, and vice versa. Since it is expensive to enumerate every two trajectories and compute their similarity, we propose <monospace> Strain-Join</monospace>, a signature-based trajectory similarity join framework. <monospace>Strain-Join</monospace> first generates signatures for each trajectory such that if two trajectories do not share common signatures, they cannot be similar. In order to utilize this property to prune dissimilar pairs, we devise several techniques to generate high-quality signatures and propose an efficient filtering algorithm to prune dissimilar pairs. For the pairs not pruned by the filtering algorithm, we propose effective verification algorithms to verify whether they are similar. Experimental results on real datasets show that our algorithm outperforms state-of-the-art techniques in terms of both effectiveness and efficiency.
登录
查看更多内容
DOI：
10.14778/1453856.1453971
发表时间：
2008-08
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
Hoyoung Jeung;Man Lung Yiu;Xiaofang Zhou;Christian S. Jensen;Heng Tao Shen
通讯作者：
Hoyoung Jeung;Man Lung Yiu;Xiaofang Zhou;Christian S. Jensen;Heng Tao Shen
基于前缀过滤的空间文本相似度连接方法
DOI：
10.1109/tkde.2013.83
发表时间：
2014-10
期刊：
IEEE Transactions on Knowledge and Data Engineering (TKDE), 2014
影响因子：
--
作者：
Sitong Liu;Guoliang Li;Jianhua Feng
通讯作者：
Jianhua Feng
DOI：
10.1109/icde.2015.7113351
发表时间：
2015-04
期刊：
2015 IEEE 31st International Conference on Data Engineering
影响因子：
--
作者：
Sayan Ranu;P Deepak;Aditya Telang;Prasad Deshpande;S. Raghavan
通讯作者：
Sayan Ranu;P Deepak;Aditya Telang;Prasad Deshpande;S. Raghavan
DOI：
10.1145/2487575.2487617
发表时间：
2013-08
期刊：
Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining
影响因子：
--
作者：
Guoliang Li;Yang Wang;Ting Wang;Jianhua Feng
通讯作者：
Guoliang Li;Yang Wang;Ting Wang;Jianhua Feng
影响因子：
2.7
作者：
Keogh, E;Ratanamahatana, CA
通讯作者：
Ratanamahatana, CA