Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

7-2020

Abstract

On-demand ride-sharing is rapidly growing. Matching trip requests to vehicles efficiently is critical for the service quality of ride-sharing. To match trip requests with vehicles, a prune-And-select scheme is commonly used. The pruning stage identifies feasible vehicles that can satisfy the trip constraints (e.g., trip time). The selection stage selects the optimal one(s) from the feasible vehicles. The pruning stage is crucial to lowering the complexity of the selection stage and to achieve efficient matching. We propose an effective and efficient pruning algorithm called GeoPrune. GeoPrune represents the time constraints of trip requests using circles and ellipses, which can be computed and updated efficiently. Experiments on real-world datasets show that GeoPrune reduces the number of vehicle candidates in nearly all cases by an order of magnitude and the update cost by two to three orders of magnitude compared to the state-of-The-Art.

Keywords

Geometric properties, Number of vehicles, Pruning algorithms, Real-world datasets, Selection stages, State of the art, Three orders of magnitude, Time constraints

Discipline

Databases and Information Systems | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

Proceedings of the 32nd International Conference on Scientific and Statistical Database Management, Virtual, Online, 2020 July 7-9

ISBN

9781450388146

Identifier

10.1145/3400903.3400912

Publisher

ACM

City or Country

New York

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1145/3400903.3400912

Download

Share

COinS