Highly scalable trip grouping for large-scale collective transportation systems
2008 (English)In: Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings / [ed] Alfons Kemper and Patrick Valduriez and Noureddine Mouaddib and Jens Teubner and Mokrane Bouzeghoub and Volker Markl and Laurent Amsaleg and Ioana Manolescu, ACM Press, 2008, Vol. 261, 678-689 p.Conference paper (Refereed)
Transportation–related problems, like road congestion, parking, and pollution, are increasing in most cities. In order to reduce traﬃc, recent work has proposed methods for vehicle sharing, for example for sharing cabs by grouping “closeby” cab requests and thus minimizing transportation cost and utilizing cab space. However, the methods published so far do not scale to large data volumes, which is necessary to facilitate large–scale collective transportation systems, e.g., ride–sharing systems for large cities.
This paper presents highly scalable trip grouping algorithms, which generalize previous techniques and support input rates that can be orders of magnitude larger. The following three contributions make the grouping algorithms scalable. First, the basic grouping algorithm is expressed as a continuous stream query in a data stream management system to allow for a very large ﬂow of requests. Second, following the divide–and–conquer paradigm, four space–partitioning policies for dividing the input data stream into sub–streams are developed and implemented using continuous stream queries. Third, using the partitioning policies, parallel implementations of the grouping algorithm in a parallel computing environment are described. Extensive experimental results show that the parallel implementation using simple adaptive partitioning methods can achieve speed–ups of several orders of magnitude without signiﬁcantly degrading the quality of the grouping.
Place, publisher, year, edition, pages
ACM Press, 2008. Vol. 261, 678-689 p.
, ACM International Conference Proceeding Series, 261
spatio-temporal data stream processing; spatio-temporal data mining, LBS, ITS
IdentifiersURN: urn:nbn:se:kth:diva-81999DOI: 10.1145/1353343.1353425ISBN: 978-1-59593-926-5OAI: oai:DiVA.org:kth-81999DiVA: diva2:499955
EDBT 2008, 11th International Conference on Extending Database Technology, Nantes, France, March 25-29, 2008
QC 201202172012-02-132012-02-112012-02-17Bibliographically approved