When Hashing Met Matching Efficient Spatio-temporal Search For Ridesharing

Dutta Chinmoy. Arxiv 2018

[Paper]    
ARXIV

Carpooling, or sharing a ride with other passengers, holds immense potential for urban transportation. Ridesharing platforms enable such sharing of rides using real-time data. Finding ride matches in real-time at urban scale is a difficult combinatorial optimization task and mostly heuristic approaches are applied. In this work, we mathematically model the problem as that of finding near-neighbors and devise a novel efficient spatio-temporal search algorithm based on the theory of locality sensitive hashing for Maximum Inner Product Search (MIPS). The proposed algorithm can find $k$ near-optimal potential matches for every ride from a pool of $n$ rides in time $O(n^{1+\rho }(k+logn)logk)$ and space $O(n^{1+\rho }logk)$ for a small $\rho <1$. Our algorithm can be extended in several useful and interesting ways increasing its practical appeal. Experiments with large NY yellow taxi trip datasets show that our algorithm consistently outperforms state-of-the-art heuristic methods thereby proving its practical applicability.

Similar Work

• Derandomized Balanced Allocation
• Asymmetric LSH (ALSH) For Sublinear Time Maximum Inner Product Search (MIPS).
• Asymmetric LSH (ALSH) For Sublinear Time Maximum Inner Product Search (MIPS)
• Clustering Is Efficient For Approximate Maximum Inner Product Search