Convoy Queries in Spatio-Temporal Databases
Speaker: Hoyoung Jeung, ITEE
When: 2007-08-01 13:00:00
Venue: 78-622
Host: Heng Tao Shen
Abstract:In this talk, we address the problem of a convoy query that
retrieves all convoys from historical trajectories, each of which
consists of a set of objects that travelled closely during a certain
time period. Convoy query is useful for many applications (e.g.,
throughput planning of delivery vehicles), however, little related
work has been done in the database community. This study formally
defines the convoy query using density-based notions in order to
avoid the drawbacks of existing solutions. We then propose three
efficient methods for discovering convoys. The main novelty of our
approaches are to approximate original trajectories by using line
simplification methods, and to bound errors by proving the Lower
Bounding Lemma. The lemma demonstrates that the Euclidean distance
between two points is lower bounded by the Euclidean distance with a
variable between the corresponding points on simplified
trajectories. Based on this lemma, we determine the error bound and
perform the discovery process over the compact trajectories without
reporting any false negatives. Furthermore, we tighten the error
bound by the combination of a spatio-temporal line simplification
and its distance measures, thus this approach is more effective and
efficient. We present comprehensive experimental results among the
proposed methods over various datasets.
Biography:(biography unavailable)
Type: DKE Seminar
Contact:Heng Tao Shen, seminar host (shenht@itee.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)