An improved algorithm for dynamic nearest-neighbour models

F.-B. Mocnik*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

12 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1-28
Number of pages28
JournalJournal of spatial science
DOIs
Publication statusE-pub ahead of print/First online - 9 Sep 2020

Keywords

  • ITC-ISI-JOURNAL-ARTICLE
  • ITC-HYBRID
  • UT-Hybrid-D

Fingerprint Dive into the research topics of 'An improved algorithm for dynamic nearest-neighbour models'. Together they form a unique fingerprint.

Cite this