I enjoyed the talk, but it doesn't actually require LSH to solve efficiently. Rephrase the question as finding those trips which start out near each other and end near each other, regardless of path taken. Use the time dimension to collapse your path into a single start lat/lon and finish lat/lon pair. The data isn't high dimensional which makes the problem very simple. Use your favorite spatial index/hash to bucket your nearest neighbors, one for trip starts, one for finishes.. Then for each bucket in starts, collect all those finishes who also share a finish index/hash. Tune the size of your spatial index/hash to achieve acceptable bucket sizes.
I think the problem (likely for Uberpool) is not to find trips which have the same start and end, but trips which overlap enough so that combining the trips won't add much time for either passenger. So if I am traveling from A -> D, and the best route is from A -> B -> C -> D, and someone else is traveling from B -> E, with the best route B -> C -> D -> E, Uber would want to match us together, because the extra pickup and dropoff won't add much time to either trip.
