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

112 Citations (Scopus)
1499 Downloads (Pure)


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


Conference2015 IEEE 31st International Conference on Data Engineering (ICDE)
Country/TerritoryKorea, Republic of


Dive into the research topics of 'Indexing and matching trajectories under inconsistent sampling rates'. Together they form a unique fingerprint.

Cite this