Efficient Top-k Matching for Publish/Subscribe Ride Hitching

Yafei Li, Hongyan Gu, Rui Chen*, Jianliang Xu, Shangwei Guo, Junxiao Xue, Mingliang Xu*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)

Abstract

With the continued proliferation of mobile Internet and geo-locating technologies, carpooling as a green transport mode is widely accepted and becoming tremendously popular worldwide. In this paper, we focus on a popular carpooling service called ride hitching , which is typically implemented using a publish/subscribe approach. In a ride hitching service, drivers subscribe ride orders published by riders and continuously receive matching ride orders until one is picked. The current systems (e.g., Didi Hitch) adopt a threshold-based approach to filter ride orders. That is, a new ride order will be sent to all subscribing drivers whose planned trips can match the ride order within a pre-defined detour threshold. A limitation of this approach is that it is difficult for drivers to specify a reasonable detour threshold in practice. In addressing this problem, we propose a novel type of top- k subscription queries called Top-kk Ride Subscription (TkRS) query, which continuously returns the best k ride orders that match drivers’ trip plans to them. We propose two efficient algorithms to enable the top- k result maintenance. We also design a novel hybrid grid index and a two-level buffer structure to efficiently track the top- k results for all TkRS queries. Finally, extensive experiments on real-life datasets suggest that our proposed algorithms are capable of achieving desirable performance in practical settings.

Original languageEnglish
Pages (from-to)3808-3821
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume35
Issue number4
Early online date2 Nov 2021
DOIs
Publication statusPublished - 1 Apr 2023

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Location-based service
  • ridesharing
  • order dispatch
  • query processing
  • optimization

Fingerprint

Dive into the research topics of 'Efficient Top-k Matching for Publish/Subscribe Ride Hitching'. Together they form a unique fingerprint.

Cite this