Averaging GPS segments

Call for papers: Special issue and Competition



Background

In recent years, navigation and location based applications have seen a rise in development. For these to work reliably, up-to-date road networks are essential. Maintaining the road networks requires extensive manual editing, which has led researchers to develop automated road network extraction methods from GPS trajectories. A common approach is to divide the task in two:
  • detecting the intersections
  • creating the road segments
This special issue focuses on the later and poses the following challenge: knowing the location of the intersections and using only the GPS trajectory segments between intersection pairs, calculate the road segment connecting such a pair.


Goal

The goal is to output a representative segment that best describes the set of input segments. It does not need to be any of the input. Instead, it should match the real road or trail where the GPS trajectories were collected.

What is it?

The objective is to find best method for averaging a given set of trajectories so that they would match ground truth segments obtained from Open Street Map. The algorithm should be both effective and efficient.
We organize the special issue as a challenge. We invite researchers and practitioners to:
  • Submit your method in the competition
  • Submit a paper to the special issue
We note that the correct segment might not always be possible to derive without using additional information such as the original GPS coordinates, their time stamps, move type, or already existing road networks and buildings. We even encourage researchers to explore such possibilities in their paper submissions. However, submissions to the challenge are not allowed to use any external data but strictly limited to the normalized segments.

It is possible to submit your method only to the competition but we recommend to submit also a paper to the special issue if the method has novelty. Paper submissions outside the competition are also allowed and not limited to the averaging problem. Paper submissions dealing with problems related to GPS trajectory analysis and road network construction are also welcome. All submitted papers will go through a normal review process.

Competition Rules:

We will provide a training set extracted from the data in [1, 2, 3, 4]. Submitted methods should work on all these segments but expected to generalize to other similar data beyond the training set. The methods are not allowed to utilize additional data others than what is included in the training dataset. In specific, external databases are forbidden. All submissions should be self-documented programs in Matlab, Python, C/C++, Java or PHP to be executed on a Linux machine. We provide templates for reading and writing the data. Each submission must contain:
  1. Source code
  2. Method description
  3. Citation (if method is existing) or a submitted paper (if the method is original)

Data:

Training data available here.

Submission system:

Submit your solutions here.

Important dates:


Competition opens: 1 Dec 2018
Deadline for algorithm submissions: 15 April 2019
Deadline for manuscript submissions: 31 August 2019
Final results: 21 June 2019
*All deadlines are at midnight, Eastern European Time

Evaluation:

All submissions will be evaluated on a different test dataset, which will be similar to the training set, but larger. The resulting segment averages will be compared with ground truth extracted from OpenStreetMap. The main criteria in the competition will be quality. The evaluation will be done by visual inspection and an objective measure that will be revealed later. Trajectory similarity will also be calculated using other measures (DTW, Hausdorff, Frechet) to gain more insight. Secondary criteria will be speed and simplicity of the algorithm. We will evaluate all methods by running them on the same Dell R920 machine with 4 x E7-4860 (total 48 cores), 1 TB, 4 TB SAS HD.

Results:

Results will be published on the competition website by 21 June 2019, latest. Intermediate results on the training data will be available already during the competition immediately after every upload. We will provide the following outcomes from the competition:
  • Two ranking lists: quality and speed (quality <10% worse than that of the winner)
  • Results will be fully documented and published later as a paper
  • All test data will also be published
  • The winner will be invited to visit the Machine Learning group at UEF. We cover reasonable travel and accommodation expenses, and provide VIP treatment during the visit . The winner also qualifies to be an IMPIT student in case he/she persues a MSc degree in Finland. Language proficiency will still need to be proved.

For more information contact the organizers:

References:

  1. R. Mariescu-Istodor and P. Fränti, "Grid-based method for GPS route analysis for retrieval" ACM Transactions on Spatial Algorithms and Systems 3 (3), July 2017.
  2. R. Mariescu-Istodor and P. Fränti. "Cellnet: Inferring road networks from gps trajectories." ACM Transactions on Spatial Algorithms and Systems 4, no. 3 (2018): 8.
  3. M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk. 2015. "A Comparison and Evaluation of Map Construction Algorithms". GeoInformatica, 19 (3), pp. 601-632.
  4. J. Biagioni and J. Eriksson. 2012. "Inferring road maps from global positioning system traces: Survey and comparative evaluation". Transportation Research Record: Journal of the Transportation Research Board, (2291), pp. 61-71.