Indexing and matching trajectories under inconsistent sampling rates
Indexing and matching trajectories under inconsistent sampling rates
复制标题
DOI：
10.1109/icde.2015.7113351
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
Sayan Ranu;P Deepak;Aditya Telang;Prasad Deshpande;S. Raghavan
中科院分区：
文献类型：
--
作者：
Sayan Ranu;P Deepak;Aditya Telang;Prasad Deshpande;S. Raghavan
轨迹相似度的量化是时空数据库分析中的一项基本操作。虽然存在一些距离函数，但最近弹道生成过程的动态变化违反了它们的核心假设之一：一致和统一的采样率。在本文中，我们提出了一种称为编辑投影距离(EDwP)的稳健距离函数，通过动态内插来匹配不一致和可变采样率下的轨迹。这是通过部署投影的想法来实现的，该投影不仅匹配采样点，同时对齐轨迹。为了使用EDwP实现高效的轨迹检索，我们设计了一个名为TrajTree的索引结构。TrajTree通过使用包围盒和Lipschitz嵌入的独特组合来获得其剪枝能力。在真实弹道数据库上的广泛实验表明，EDwP比最先进的距离函数的精度高达5倍。此外，TrajTree比现有技术提高了轨迹检索的效率高达一个数量级。
Quantifying the similarity between two trajectories is a fundamental operation in analysis of spatio-temporal databases. While a number of distance functions exist, the recent shift in the dynamics of the trajectory generation procedure violates one of their core assumptions; a consistent and uniform sampling rate. In this paper, we formulate a robust distance function called Edit Distance with Projections (EDwP) to match trajectories under inconsistent and variable sampling rates through dynamic interpolation. This is achieved by deploying the idea of projections that goes beyond matching only the sampled points while aligning trajectories. To enable efficient trajectory retrievals using EDwP, we design an index structure called TrajTree. TrajTree derives its pruning power by employing the unique combination of bounding boxes with Lipschitz embedding. Extensive experiments on real trajectory databases demonstrate EDwP to be up to 5 times more accurate than the state-of-the-art distance functions. Additionally, TrajTree increases the efficiency of trajectory retrievals by up to an order of magnitude over existing techniques.