Discovery of convoys in trajectory databases

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

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

306 Citations (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.

Original languageEnglish
Title of host publicationProceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand
Number of pages13
PublisherAssociation for Computing Machinery
Publication date2008
Pages1068-1080
ISBN (Print)978-1-60558-305-1
DOIs
Publication statusPublished - 2008
Event34th International Conference on Very Large Data bases - Auckland, New Zealand
Duration: 23 Aug 200828 Aug 2008
Conference number: 34

Conference

Conference34th International Conference on Very Large Data bases
Number34
CountryNew Zealand
CityAuckland
Period23/08/200828/08/2008

Fingerprint

Trajectories
Mobile devices
Information management
Trucks
Throughput
Planning

Cite this

Jeung, H., Yiu, M. L., Zhou, X., Jensen, C. S., & Shen, H. T. (2008). Discovery of convoys in trajectory databases. In Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand (pp. 1068-1080). Association for Computing Machinery. https://doi.org/10.1145/1453856.1453971
Jeung, Hoyoung ; Yiu, Man Lung ; Zhou, Xiaofang ; Jensen, Christian Søndergaard ; Shen, Heng Tao. / Discovery of convoys in trajectory databases. Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand. Association for Computing Machinery, 2008. pp. 1068-1080
@inproceedings{bdeb9b60d5be11dda016000ea68e967b,
title = "Discovery of convoys in trajectory databases",
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.",
author = "Hoyoung Jeung and Yiu, {Man Lung} and Xiaofang Zhou and Jensen, {Christian S{\o}ndergaard} and Shen, {Heng Tao}",
year = "2008",
doi = "10.1145/1453856.1453971",
language = "English",
isbn = "978-1-60558-305-1",
pages = "1068--1080",
booktitle = "Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand",
publisher = "Association for Computing Machinery",
address = "United States",

}

Jeung, H, Yiu, ML, Zhou, X, Jensen, CS & Shen, HT 2008, Discovery of convoys in trajectory databases. in Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand. Association for Computing Machinery, pp. 1068-1080, 34th International Conference on Very Large Data bases, Auckland, New Zealand, 23/08/2008. https://doi.org/10.1145/1453856.1453971

Discovery of convoys in trajectory databases. / Jeung, Hoyoung; Yiu, Man Lung; Zhou, Xiaofang; Jensen, Christian Søndergaard; Shen, Heng Tao.

Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand. Association for Computing Machinery, 2008. p. 1068-1080.

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Discovery of convoys in trajectory databases

AU - Jeung, Hoyoung

AU - Yiu, Man Lung

AU - Zhou, Xiaofang

AU - Jensen, Christian Søndergaard

AU - Shen, Heng Tao

PY - 2008

Y1 - 2008

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

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

U2 - 10.1145/1453856.1453971

DO - 10.1145/1453856.1453971

M3 - Article in proceeding

SN - 978-1-60558-305-1

SP - 1068

EP - 1080

BT - Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand

PB - Association for Computing Machinery

ER -

Jeung H, Yiu ML, Zhou X, Jensen CS, Shen HT. Discovery of convoys in trajectory databases. In Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand. Association for Computing Machinery. 2008. p. 1068-1080 https://doi.org/10.1145/1453856.1453971