Problem Definition

Input: A file dataset.txt containing paths to trajectory files making up the dataset. Each referenced files is in a SSV format with the two first columns holding coordinates for X and Y. Note that time stamps are not given as the Fréchet distance does not incorporate absolute time.

Parameters: A file queries.txt containing pairs of a query trajectory file names (as given in dataset.txt) and Fréchet distance bounds .

Output: A set of file names for each query written to result-XXXX.txt, where XXXX stands for the line number of the query (starting with 0).


  • Irrespective of the actual nature of the coordinates (e.g., WGS84), we will always use Euclidean distance between the coordinates in the x and y column of the dataset.

  • The order of the returned file names can be arbitrary

Evaluation Criteria

All submissions are evaluated for their correctness and average performance on a various large trajectory databases and queries. The used datasets are similar to the sample dataset, but can be much smaller or larger. We will test all submission with increasing numbers of queries on varying sizes created by the method explained on the download page. Your program should expect the number of queries to be a fixed number between 100 and 100,000. Hence, you can afford to build spatial indices for the dataset, as many queries are to be answered. You are not allowed to serialize any information between different runs. We will use the total elapsed wall clock time as a measure of performance. For breaking ties, we will first look into the scalability behavior for more and more queries on larger and larger datasets. Finally, we break ties on code stability, quality, and readability and by using different datasets.