# Trip Matching - our methods

I'm curious how the other teams in the top 5 did it.  We received a pretty good boost by matching trips.  I did several different methods, I think this was the order I did them in, but I'm sure I'm forgetting some dead ends.
Approach 0:
Align the start and end to the x axis.
Approach 1:
Simplify trips using RDP (Ramer–Douglas–Peucker), then create just a list of the distances between turns over a threshold along with a second list giving the size of the turn - ignore right or left.  This is a great first pass - very quick and you can weed out a lot of trips this way  I would compare forward and backward (this solved the starting from 0,0 every time bit) just looking at distance between turns, then compare the size of the turn within a threshold (this ignores mirroring) - all together that took care of rotation as well.  We used 42 sets of tolerances for RDP and angles - at one point I think I was up to 180 tolerance / angle pairs, but found most were redundant and wasted time.
By setting a minimum number of required turns to match we could generate quickly a set of matches.  Testing revealed this worked very well.  I can't recall the jump, but when I first teamed up with Ben we went from 11th to 3rd using just an override setting matches to 1.0's  - the most basic way of using matches.
Approach 2:
Widen the matching angle to find more matches, then use Dynamic Time Warping to score the trips.  This worked OK, but not really any better.
Approach 3:
Interpolate the trip into points spaced at an even interval, then trip DTW, this just couldn't score better than approach 1.
Approach 4:
Align the matched sub-trips based on the locations of the turns, and use Singular Value Decomposition to align the sub-trips and get the RSME error for the points.  This worked very well.
Approach 5:
Keep track of who matches to whom - an adjacency tree, use it to create clusters of matched trips.  Try various features based on the size of the cluster a trip is in, even did a page rank style analysis of the match trip network...maybe I wasn't smart enough but that feature didn't help (though we didn't start using it until the last 2 days or so, not much time to adjust it).
Approach 6:
Use use RDP turn / angle approximations and SVD for alignment, score with RSME for the sub-trip, then align the full trip and measure the distance between the start and end of the trip.
Approach 6a:
If we know the adjacency tree to walk from one trip to another we can rotate and align all the trips in a cluster to each other!  Then by viewing the map of the driver's matches we could adjust the parameters for RSME and the minimum distance between the start and end of a trip (to account for trimming). If the minimum distance between the start or end of the aligned trip is greater than a certain value, ignore the match.  It's a really elegant idea (if I do say so myself) and it failed [edit, turns out it failed when used as a feature giving to our ML classifier, however I've done a few more submissions now that the contest is over, with the matches from this approach boosting the classifier's results and turns out this would have worked]....in the end just using an RSME score for the sub-trip alignment found by SVD worked best.
Take away - RDP to simplify the trip, break up into distances between turns (rounded to the nearest 100 meters), record turn sizes (not directions), look for matches forward, backward and with some allowance for slightly larger / smaller turns, then align using SVD, compare the alignment, keep track of how many matches a trip has, and in the end feed that feature fed into a ML algorithm - worked well.
The speed of the basic method made it possible to check for matches between all the drivers.  Starting with the bottom 50,000 (per our classifier) but in the end I ran it on on all matches paired against each other, on a i7 quad core it would take about 20 hours.
I would later move onto EC2 clusters which made it possible to iterate over small changes in the algorithm and have the results in 1 to 2 hours for a basic version - last night I had 16 machines running at one time, eleven - 32 core machines and five - 36 core machines - managed to run two different matching algorithms in about 3.5 hours total - one of which helped us to finally climb over 97%.