A testbed for evaluating network construction algorithms from GPS traces. (November 2017)

• Record Type: Journal Article
• Authors: Hashemi, Mahdi
• Is Part Of: Computers, environment and urban systems. Volume 66(2017)
• Page Start: 96
• Page End: 109
• Publication Date: 2017-11
• Subjects: Network construction -- Street network -- Pedestrian network -- GPS data -- Spatial data mining -- Artificial intelligence; City planning -- Data processing -- Periodicals; Regional planning -- Data processing -- Periodicals; 303.4834
• DOI: 10.1016/j.compenvurbsys.2017.08.003
• Languages: English
• ISSNs: 0198-9715

Abstract

Abstract: 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. Highlights: Establishing a testbed for evaluating network construction algorithms Providing street and pedestrian networks with different densities and complexities Providing collections of GPS traces with different accuracies and sampling rates Developing completeness, precision, and topology correctness metrics for networks