Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015 |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 999-1010 |
Number of pages | 12 |
ISBN (Print) | 978-1-4799-7963-9 |
DOIs | |
Publication status | Published - Apr 2015 |
Event | 2015 IEEE 31st International Conference on Data Engineering (ICDE) - Seoul, Korea, Republic of Duration: 13 Apr 2015 → 17 Apr 2015 |
Conference
Conference | 2015 IEEE 31st International Conference on Data Engineering (ICDE) |
---|---|
Country/Territory | Korea, Republic of |
City | Seoul |
Period | 13/04/2015 → 17/04/2015 |