IEEE ICDM Traffic Contest - Solutions, part 2

we publish further descriptions of top solutions of the IEEE ICDM Contest: TomTom Traffic Prediction for Intelligent GPS Navigation. This time you may read reports on Task 2 "Jams" and Task 3 "GPS". Solutions of Task 1 can be found in Part 1.

Task 2: "Jams"

By Łukasz Romaszko (lukasz21212121), the winner, from the University of Warsaw, Poland.

The algorithm focuses on computing ranks for each street (the higher rank means greater probability of traffic jam) and the number of streets to be jammed. The highest ranked streets are given as the output. In particular it uses an adaptation of the k-Nearest Neighbors algorithm. The following description of the algorithm is simplified. The scheme presenting the algorithm idea is given below.

Computing street ranks and the number p of jammed streets consists of several steps. From the training data set there are chosen two ordered sets: Similarity and LengthSimilarity. Similarity is used to compute street ranks, while LengthSimilarity to determinate number p. On the basis of Similarity set and special functions algorithm generates an array RankingList. In the next step RankingList will be slightly modified by taking into consideration the locations of streets. The top p streets are given as the output. ...

Task 3 "GPS"

By Benjamin Hamner (hamner), the winner. Benjamin recently completed his bachelors degree at Duke University and is currently doing research at the EPFL, Lausanne, Switzerland, on a Whitaker Fellowship.

Transforming GPS Coordinates to Road Segments

An algorithm was developed to rapidly determine which road segment a car was on given its GPS coordinate. The roads in Warsaw were preprocessed by laying a grid of points over the map and determining which road segments lay within a certain radius. This meant that, given a GPS coordinate, only the distance to road segments near the four closest grid points to the GPS coordinate needed evaluation. The preprocessing was reiterated with finer grids of points.

Though there are surely faster algorithms, this worked - it allowed the 200 million GPS readings in the competition data set to be transformed to road segments in under two days, instead of several years for the brute force approach. No corrections were made for GPS coordinates outside of Warsaw, which likely had a slight negative impact on the results.

Read more.