Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis Yongxin Tong 1, Jieying She 2, Bolin Ding 3, Lei Chen Tianyu Wo1, Ke Xu 1 Beihang University The Hong Kong University of Science and Technology 3 Microsoft Research ”京航堂航天学而恐楼欢眼 Microsoft BEIHANG UNIVERSITY SCIENCE AND TECHNOLOGY Research
Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis Yongxin Tong 1 , Jieying She 2 , Bolin Ding 3 , Lei Chen 2 , Tianyu Wo 1 , Ke Xu 1 1 Beihang University 2 The Hong Kong University of Science and Technology 3 Microsoft Research
Outline o Background and Motivation ● Problem statement o Representative algorithms o The greedy algorithm Revisited ● Experiments Conclusion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Representative Algorithms ⚫ The Greedy Algorithm Revisited ⚫ Experiments ⚫ Conclusion
Minimum Bipartite Matching(MBM) The problem of minimum bipartite matching MBM)in spatial data is a fundamental issue
⚫ The problem of minimum bipartite matching (MBM) in spatial data is a fundamental issue Minimum Bipartite Matching (MBM)
Minimum Bipartite Matching(MBM) The problem of minimum bipartite matching MBM)in spatial data is a fundamental issue Given a set of service providers and a set of users in a 2D space Y (5,5) 5 W3(3,4) t3(5,5) W2(2,3) t2(2,3)t4(5,3) t1(1,2) W1(3,0) 12345X
⚫ The problem of minimum bipartite matching (MBM) in spatial data is a fundamental issue ⚫ Given a set of service providers and a set of users in a 2D space. Minimum Bipartite Matching (MBM) t1（1，2） t2（2，3） w2（2，3） w3（3，4） w1（3，0） w4（5，5） t3（5，5） t4（5，3） 5 4 3 2 1 1 2 3 4 5 Y X
Minimum Bipartite Matching(MBM) The problem of minimum bipartite matching MBM)in spatial data is a fundamental issue Given a set of service providers and a set of users in a 2D space The MBM problem is to find a maximum-cardinality matching with minimum total distance between the matched pairs Y (5,5) 5432 W3(3,4) t3(5,5) W2(2,3) t2(2,3)t4(5,3) t1(1,2) W1(3,0) Optimal Matching 12345X
⚫ The problem of minimum bipartite matching (MBM) in spatial data is a fundamental issue ⚫ Given a set of service providers and a set of users in a 2D space. ⚫ The MBM problem is to find a maximum-cardinality matching with minimum total distance between the matched pairs. Minimum Bipartite Matching (MBM) t1（1，2） t2（2，3） w2（2，3） w3（3，4） w1（3，0） w4（5，5） t3（5，5） t4（5，3） 5 4 3 2 1 1 2 3 4 5 Y X 𝑤1 𝑤2 𝑤3 𝑡1 𝑡2 𝑡3 𝑤4 𝑡4 Optimal Matching
Online Minimum Bipartite Matching(OMBM Recently, most applications of the MBM issue need to be addressed in real-time, which is called the online MBM(OMBM) problem CAR 神州专车 ∪BER DIDi More than a journey
⚫ Recently, most applications of the MBM issue need to be addressed in real-time, which is called the online MBM (OMBM) problem Online Minimum Bipartite Matching (OMBM)
Online Minimum Bipartite Matching(OMBM Recently, most applications of the MBM issue need to be addressed in real-time, which is called the online MBM(OMBM) problem CAR Gigal 神州荟车 ∪BER taskrabbit zy Life is busy. We hel DiDi grubHub happy eating aze
⚫ Recently, most applications of the MBM issue need to be addressed in real-time, which is called the online MBM (OMBM) problem Online Minimum Bipartite Matching (OMBM)
9 Challenges of the OMBM Problem o Real-time taxi-calling services usually adopt nearest neighbor (NN strategy to address the mbm issues Once a task appears, it should be assigned immediately 的标 有+Q确工 A知 金曰: 青云北 有 。一: The cost of the m nN strategy ia. 友道社 各
The cost of the NN strategy ⚫ Real-time taxi-calling services usually adopt ‘nearest neighbor (NN)’ strategy to address the OMBM issues. ⚫ Once a task appears, it should be assigned immediately. Challenges of the OMBM Problem 9
10 Challenges of the OMBM Problem Real-time taxi-calling services usually adopt nearest neighbor(NN strategy to address task assignment issues. Once a task appears, it should be assigned immediately. If we know everything in advance, the offline oPt is shown 是1 容 青五北区 The offline 定棒树北 cost 大 m 出 小肃社区 友社 中A
⚫ Real-time taxi-calling services usually adopt ‘nearest neighbor (NN)’ strategy to address task assignment issues. ⚫ Once a task appears, it should be assigned immediately. ⚫ If we know everything in advance, the offline OPT is shown. Challenges of the OMBM Problem The offline cost 10
Contributions of our work Inspired by many observations in applications and a comprehensive experimental study of the OMBM problem, our contributions are Motivations Contributions 1 Is Greedy really the worst? Greedy has good performance Is the worst-case analysis 2 appropriate for the OMB Worst-case VS. Average-case analysIs problem in practice? Are implementations and 3 experimental evaluations Uniform implementations and evaluations are provided uniform? Open question: the average-case approximation ratio (aka competitive ratio) of the simple greedy algorithm for the OMBM problem should be constant
⚫ Inspired by many observations in applications and a comprehensive experimental study of the OMBM problem, our contributions are Contributions of Our Work 11 Motivations Contributions 1 Is Greedy really the worst?Greedy has good performance. 2 Is the worst-case analysis appropriate for the OMBM problem in practice? Worst-case vs. Average-case analysis. 3 Are implementations and experimental evaluations uniform? Uniform implementations and evaluations are provided. Open question: the average-case approximation ratio (a.k.a competitive ratio) of the simple greedy algorithm for the OMBM problem should be constant!