A testbed for evaluating network construction algorithms from GPS traces

Developing algorithms which construct street/pedestrian networks from crowd-sourced GPS traces has been an ongoing research since the outbreak of inexpensive GPS receivers on mobile devices. Although, the proposed algorithms are evaluated by their developers, the evaluation results cannot be used to compare their accuracy because: (a) different algorithms target different types of networks, some designed for complicated networks while others for simple ones, (b) GPS traces, used in different studies, are not the same, some of them are more accurate and denser than others, and (c) the constructed networks are evaluated either qualitatively or with different quantitative metrics. Lack of a comprehensive testbed for evaluating network construction algorithms has made it difficult for authors, reviewers, and readers to monitor the effectiveness of such algorithms. This study establishes a testbed for evaluating network construction algorithms containing three components: (a) street and pedestrian networks with different densities and complexities as the baseline, (b) collections of GPS traces with different accuracies and sampling rates to be used by algorithms to construct those networks, and (c) three quantitative metrics to indicate the completeness, precision, and topology correctness of the constructed network, in addition to the algorithm's time complexity, conventionally used to indicate its time performance. This testbed not only paves the way for comparing network construction algorithms but also allows researchers to focus on their algorithms rather than collecting data for testing it or looking for ways to describe its accuracy.