TY - JOUR
T1 - Efficient Top-k Matching for Publish/Subscribe Ride Hitching
AU - Li, Yafei
AU - Gu, Hongyan
AU - Chen, Rui
AU - Xu, Jianliang
AU - Guo, Shangwei
AU - Xue, Junxiao
AU - Xu, Mingliang
N1 - Funding information:
This work was supported by NSFC Grants 61972362, 61602420, 62072136, and 62036010, HNSF Grant 202300410378, Fundamental Research Funds for the Central Universities Grant 3072020CFT2402, Guangdong Basic and Applied Basic Research Foundation Grant 2019B1515130001, and HK RGC Grant 12201018. Data source: Didi Chuxing.
Publisher copyright:
© 2021 IEEE.
PY - 2023/4/1
Y1 - 2023/4/1
N2 - 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.
AB - 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.
KW - Location-based service
KW - ridesharing
KW - order dispatch
KW - query processing
KW - optimization
UR - http://www.scopus.com/inward/record.url?scp=85118652633&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2021.3124232
DO - 10.1109/TKDE.2021.3124232
M3 - Journal article
AN - SCOPUS:85118652633
SN - 1041-4347
VL - 35
SP - 3808
EP - 3821
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 4
ER -
