We study the problem of matching rides in a ride sharing platform. Such platforms face the daunting combinatorial task of finding potential matches for rides from a matching pool of tens of thousands of rides very efficiently while retaining near-optimality compared to an exhaustive search. We formalize this problem and present a novel algorithm for it based on the beautiful theory of locality sensitive hashing for Maximum Inner Product Search (MIPS). The proposed algorithm can find $k$ (can be practically a constant for ride sharing platforms) potential matches for a given ride from a pool of $n$ rides in sub-linear time $O(n^\rho (k + \log n) \log k)$ for $\rho < 1$, which is significant saving compared to an exhaustive search in the pool requiring $O(n)$ time. The space requirement for our algorithm is $O(n^{1 + \rho} \log k)$. We show that the set of $k$ potential matches include the near-optimal ones with high probability. Implementation of our algorithm could efficiently find near-optimal set of potential matches with high probability from a pool of thousands of real rides.
from cs updates on arXiv.org https://ift.tt/2oWQSzf
//
0 comments:
Post a Comment