When Hashing Met Matching: Efficient Search for Potential Matches in Ride Sharing
share
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^ρ (k + n) k) for ρ < 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 + ρ 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.
READ FULL TEXT