Tuesday, 11 September 2018

When Hashing Met Matching: Efficient Search for Potential Matches in Ride Sharing. (arXiv:1809.02680v1 [cs.DS])

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
//

Related Posts:

0 comments:

Post a Comment