An improved algorithm for dynamic nearest-neighbour models. Issue 3 (2nd September 2022)

• Record Type: Journal Article
• Authors: Mocnik, Franz-Benjamin
• Is Part Of: Journal of spatial science. Volume 67:Issue 3(2022)
• Page Start: 411
• Page End: 438
• Publication Date: 2022-09-02
• Subjects: Nearest-neighbour model -- kNN -- fixed-radius near neighbour -- Mocnik model -- spatial network -- spatial structure -- Tobler's law; Geographic information systems -- Periodicals; Cartography -- Periodicals; Surveying -- Periodicals; Geodesy -- Periodicals; Photogrammetry -- Periodicals; Cartography; Geodesy; Geographic information systems; Photogrammetry; Surveying; Periodicals; 526.05
• DOI: 10.1080/14498596.2020.1739575
• Languages: English
• ISSNs: 1449-8596

Abstract

ABSTRACT: The naïve algorithm for generating nearest-neighbour models determines the distance between every pair of nodes, resulting in quadratic running time. Such time complexity is common among spatial problems and impedes the generation of larger spatial models. In this article, an improved algorithm for the Mocnik model, an example of nearest-neighbour models, is introduced. Instead of solving k nearest-neighbour problems for each node ( k dynamic in the sense that it varies among the nodes), the improved algorithm presented exploits the notion of locality through introducing a corresponding spatial index, resulting in a linear average-case time complexity. This makes possible to generate very large prototypical spatial networks, which can serve as testbeds to evaluate and improve spatial algorithms, in particular, with respect to the optimization of algorithms towards big geospatial data.