Indexing and matching trajectories under inconsistent sampling rates

Sayan Ranu, Deepak Padmanabhan, Aditya D. Telang, Prasad Deshpande, Sriram Raghavan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Citations (Scopus)

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.
LanguageEnglish
Title of host publicationProceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages999-1010
Number of pages12
ISBN (Print)978-1-4799-7963-9
DOIs
Publication statusPublished - Apr 2015
Event2015 IEEE 31st International Conference on Data Engineering (ICDE) - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015

Conference

Conference2015 IEEE 31st International Conference on Data Engineering (ICDE)
CountryKorea, Republic of
CitySeoul
Period13/04/201517/04/2015

Fingerprint

Trajectories
Sampling
Interpolation
Experiments

Cite this

Ranu, S., Padmanabhan, D., Telang, A. D., Deshpande, P., & Raghavan, S. (2015). Indexing and matching trajectories under inconsistent sampling rates. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015 (pp. 999-1010). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICDE.2015.7113351
Ranu, Sayan ; Padmanabhan, Deepak ; Telang, Aditya D. ; Deshpande, Prasad ; Raghavan, Sriram. / Indexing and matching trajectories under inconsistent sampling rates. Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015. Institute of Electrical and Electronics Engineers (IEEE), 2015. pp. 999-1010
@inproceedings{b548ef908c7c4b28ba2c160b8c1c13e1,
title = "Indexing and matching trajectories under inconsistent sampling rates",
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.",
author = "Sayan Ranu and Deepak Padmanabhan and Telang, {Aditya D.} and Prasad Deshpande and Sriram Raghavan",
year = "2015",
month = "4",
doi = "10.1109/ICDE.2015.7113351",
language = "English",
isbn = "978-1-4799-7963-9",
pages = "999--1010",
booktitle = "Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

}

Ranu, S, Padmanabhan, D, Telang, AD, Deshpande, P & Raghavan, S 2015, Indexing and matching trajectories under inconsistent sampling rates. in Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015. Institute of Electrical and Electronics Engineers (IEEE), pp. 999-1010, 2015 IEEE 31st International Conference on Data Engineering (ICDE), Seoul, Korea, Republic of, 13/04/2015. https://doi.org/10.1109/ICDE.2015.7113351

Indexing and matching trajectories under inconsistent sampling rates. / Ranu, Sayan; Padmanabhan, Deepak; Telang, Aditya D.; Deshpande, Prasad; Raghavan, Sriram.

Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015. Institute of Electrical and Electronics Engineers (IEEE), 2015. p. 999-1010.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Indexing and matching trajectories under inconsistent sampling rates

AU - Ranu, Sayan

AU - Padmanabhan, Deepak

AU - Telang, Aditya D.

AU - Deshpande, Prasad

AU - Raghavan, Sriram

PY - 2015/4

Y1 - 2015/4

N2 - 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.

AB - 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.

U2 - 10.1109/ICDE.2015.7113351

DO - 10.1109/ICDE.2015.7113351

M3 - Conference contribution

SN - 978-1-4799-7963-9

SP - 999

EP - 1010

BT - Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

Ranu S, Padmanabhan D, Telang AD, Deshpande P, Raghavan S. Indexing and matching trajectories under inconsistent sampling rates. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, ICDE 2015. Institute of Electrical and Electronics Engineers (IEEE). 2015. p. 999-1010 https://doi.org/10.1109/ICDE.2015.7113351