Discovery of convoys in trajectory databases

Hoyoung Jeung, Man Lung Yiu, Xiaofang Zhou, Christian Søndergaard Jensen, Heng Tao Shen

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

389 Citationer (Scopus)

Abstract

As mobile devices with positioning capabilities continue to proliferate, data management for so-called trajectory databases that capture the historical movements of populations of moving objects becomes important. This paper considers the querying of such databases for convoys, a convoy being a group of objects that have traveled together for some time.

More specifically, this paper formalizes the concept of a convoy query using density-based notions, in order to capture groups of arbitrary extents and shapes. Convoy discovery is relevant for real-life applications in throughput planning of trucks and carpooling of vehicles. Although there has been extensive research on trajectories in the literature, none of this can be applied to retrieve correctly exact convoy result sets. Motivated by this, we develop three efficient algorithms for convoy discovery that adopt the well-known filter-refinement framework. In the filter step, we apply line-simplification techniques on the trajectories and establish distance bounds between the simplified trajectories. This permits efficient convoy discovery over the simplified trajectories without missing any actual convoys. In the refinement step, the candidate convoys are further processed to obtain the actual convoys. Our comprehensive empirical study offers insight into the properties of the paper's proposals and demonstrates that the proposals are effective and efficient on real-world trajectory data.

OriginalsprogEngelsk
TitelProceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand
Antal sider13
ForlagAssociation for Computing Machinery
Publikationsdato2008
Sider1068-1080
ISBN (Trykt)978-1-60558-305-1
DOI
StatusUdgivet - 2008
Begivenhed34th International Conference on Very Large Data bases - Auckland, New Zealand
Varighed: 23 aug. 200828 aug. 2008
Konferencens nummer: 34

Konference

Konference34th International Conference on Very Large Data bases
Nummer34
Land/OmrådeNew Zealand
ByAuckland
Periode23/08/200828/08/2008

Fingeraftryk

Dyk ned i forskningsemnerne om 'Discovery of convoys in trajectory databases'. Sammen danner de et unikt fingeraftryk.

Citationsformater