Technical Report CSI-0069

Spatial and Temporal Complexity Comparisons and Scalability Investigations of Eden-like Simulation Models using Lattices, Lists and Trees

L. R. F. Odiam and K. A. Hawick

Archived: 2017

Abstract

Spatial agent-based models (ABMs) and cellular automata such as the Eden Growth Model and the Invasion Percolation Model(IP) can be formulated in terms of a list containing prioritised growth sites around an active spatial core which comprise the computational domain. These models can be implemented using dense spatial lattice structures which waste space but aid rapid spatial indexing, list data structures which avoid wasted space but which require additional searching, or spatial trees such as binary search trees which provide compromises. Eden and IP are stochastic models and use lists as part of the underpinning model itself to rank growth sites by different factors such as probability in the case of IP. We explore the trade-off space in spatial (memory) and temporal (time) complexity as well as practical implementation issues for these simulations when used to generate large numbers of large-scale aggregates and the computational issues for computing growth and metrics for assessing their emergent properties as part of complex systems numerical experimental studies. In this paper we access the memory and time consumption of the different data structure at varying grid sizes in an attempt to give a quantifiable justification for the selection of a specific data structure for the implementation of the Eden and IP models or a model that is very similar in its storage and searching requirements, this has been done as it is not always the most common sense selection for that job that turns out to be the best.

Keywords: Key Words and Phrases: complexity, scalability, memory complexity, time complexity, list, array, tree, data structures, eden growth model, invasion percolation

Full Document Text: Not yet available.

Citation Information: BiBTeX database for CSI Notes.

BiBTeX reference:

@TechReport{CSI-0069,
        Title = {Spatial and Temporal Complexity Comparisons and Scalability Investigations of Eden-like Simulation Models using Lattices, Lists and Trees},
        Author = {L. R. F. Odiam and K. A. Hawick},
        Institution = {Computer Science, University of Hull},
        Year = {2017},
        Address = {Cottingham Road, Hull, HU6 7RX},
        Month = {August},
        Number = {CSI-0069},
        Type = {Computational Science},
        Keywords = {Key Words and Phrases: complexity, scalability, memory complexity, time complexity, list, array, tree, data structures, eden growth model, invasion percolation},
        Owner = {kahawick},
        Timestamp = {2017.07.16}
}