Efficient similarity join of large sets of moving object trajectories

Hui Ding*, Goce P Trajcevski, Peter I Scheuermann

*Corresponding author for this work

Research output: Contribution to conferencePaper

25 Citations (Scopus)

Abstract

We address the problem of performing efficient similarity join for large sets of moving objects trajectories. Unlike previous approaches which use a dedicated index in a transformed space, our premise is that in many applications of location-based services, the trajectories are already indexed in their native space, in order to facilitate the processing of common spatio-temporal querìes, e.g., range, nearest neighbor etc. We, introduce a novel distance measure adapted from the classìc Frèchet distance, which can be naturally extended to support lower/upper bounding using the underlying indices of moving object databases in the native space. This, in turn, enables efficient implementation of various trajectory similarity joins. We report on extensive experiments demonstrating that our methodology provides performance speed-up of trajectory similarity join by more than 50% on average, while maintaining effectiveness comparable to the well-known approaches for identifying trajectory similarity based on time-series analysis.

Original languageEnglish (US)
Pages79-87
Number of pages9
DOIs
StatePublished - Sep 17 2008
Event15th International Symposium on Temporal Representation and Reasoning, TIME 2008 - Montreal, QC, Canada
Duration: Jun 16 2008Jun 18 2008

Other

Other15th International Symposium on Temporal Representation and Reasoning, TIME 2008
CountryCanada
CityMontreal, QC
Period6/16/086/18/08

Fingerprint

Moving Objects
Large Set
Join
Trajectory
Time Series Analysis
Distance Measure
Efficient Implementation
Nearest Neighbor
Speedup
Similarity
Methodology
Range of data
Experiment

ASJC Scopus subject areas

  • Mathematics(all)

Cite this

Ding, H., Trajcevski, G. P., & Scheuermann, P. I. (2008). Efficient similarity join of large sets of moving object trajectories. 79-87. Paper presented at 15th International Symposium on Temporal Representation and Reasoning, TIME 2008, Montreal, QC, Canada. https://doi.org/10.1109/TIME.2008.25
Ding, Hui ; Trajcevski, Goce P ; Scheuermann, Peter I. / Efficient similarity join of large sets of moving object trajectories. Paper presented at 15th International Symposium on Temporal Representation and Reasoning, TIME 2008, Montreal, QC, Canada.9 p.
@conference{b3b9a87ce9db4f50ad1a17484371e3dd,
title = "Efficient similarity join of large sets of moving object trajectories",
abstract = "We address the problem of performing efficient similarity join for large sets of moving objects trajectories. Unlike previous approaches which use a dedicated index in a transformed space, our premise is that in many applications of location-based services, the trajectories are already indexed in their native space, in order to facilitate the processing of common spatio-temporal quer{\`i}es, e.g., range, nearest neighbor etc. We, introduce a novel distance measure adapted from the class{\`i}c Fr{\`e}chet distance, which can be naturally extended to support lower/upper bounding using the underlying indices of moving object databases in the native space. This, in turn, enables efficient implementation of various trajectory similarity joins. We report on extensive experiments demonstrating that our methodology provides performance speed-up of trajectory similarity join by more than 50{\%} on average, while maintaining effectiveness comparable to the well-known approaches for identifying trajectory similarity based on time-series analysis.",
author = "Hui Ding and Trajcevski, {Goce P} and Scheuermann, {Peter I}",
year = "2008",
month = "9",
day = "17",
doi = "10.1109/TIME.2008.25",
language = "English (US)",
pages = "79--87",
note = "15th International Symposium on Temporal Representation and Reasoning, TIME 2008 ; Conference date: 16-06-2008 Through 18-06-2008",

}

Ding, H, Trajcevski, GP & Scheuermann, PI 2008, 'Efficient similarity join of large sets of moving object trajectories' Paper presented at 15th International Symposium on Temporal Representation and Reasoning, TIME 2008, Montreal, QC, Canada, 6/16/08 - 6/18/08, pp. 79-87. https://doi.org/10.1109/TIME.2008.25

Efficient similarity join of large sets of moving object trajectories. / Ding, Hui; Trajcevski, Goce P; Scheuermann, Peter I.

2008. 79-87 Paper presented at 15th International Symposium on Temporal Representation and Reasoning, TIME 2008, Montreal, QC, Canada.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Efficient similarity join of large sets of moving object trajectories

AU - Ding, Hui

AU - Trajcevski, Goce P

AU - Scheuermann, Peter I

PY - 2008/9/17

Y1 - 2008/9/17

N2 - We address the problem of performing efficient similarity join for large sets of moving objects trajectories. Unlike previous approaches which use a dedicated index in a transformed space, our premise is that in many applications of location-based services, the trajectories are already indexed in their native space, in order to facilitate the processing of common spatio-temporal querìes, e.g., range, nearest neighbor etc. We, introduce a novel distance measure adapted from the classìc Frèchet distance, which can be naturally extended to support lower/upper bounding using the underlying indices of moving object databases in the native space. This, in turn, enables efficient implementation of various trajectory similarity joins. We report on extensive experiments demonstrating that our methodology provides performance speed-up of trajectory similarity join by more than 50% on average, while maintaining effectiveness comparable to the well-known approaches for identifying trajectory similarity based on time-series analysis.

AB - We address the problem of performing efficient similarity join for large sets of moving objects trajectories. Unlike previous approaches which use a dedicated index in a transformed space, our premise is that in many applications of location-based services, the trajectories are already indexed in their native space, in order to facilitate the processing of common spatio-temporal querìes, e.g., range, nearest neighbor etc. We, introduce a novel distance measure adapted from the classìc Frèchet distance, which can be naturally extended to support lower/upper bounding using the underlying indices of moving object databases in the native space. This, in turn, enables efficient implementation of various trajectory similarity joins. We report on extensive experiments demonstrating that our methodology provides performance speed-up of trajectory similarity join by more than 50% on average, while maintaining effectiveness comparable to the well-known approaches for identifying trajectory similarity based on time-series analysis.

UR - http://www.scopus.com/inward/record.url?scp=51549120438&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51549120438&partnerID=8YFLogxK

U2 - 10.1109/TIME.2008.25

DO - 10.1109/TIME.2008.25

M3 - Paper

SP - 79

EP - 87

ER -

Ding H, Trajcevski GP, Scheuermann PI. Efficient similarity join of large sets of moving object trajectories. 2008. Paper presented at 15th International Symposium on Temporal Representation and Reasoning, TIME 2008, Montreal, QC, Canada. https://doi.org/10.1109/TIME.2008.25