A comparison of neuron touch detection algorithms utilising voxelization and the data structures octree, k-d tree and R-tree

Sammanfattning: Simulations of biologically detailed neuronal networks have become an essential tool in the study of the brain. An important step in the creation of these types of simulations is the detection of the connections between the nerve cells. This paper analyses the efficiency of four algorithms used for such purposes. Three of them are based on space-partitioning data structures commonly adopted for solving similar optimization problems, namely Octree, R tree and k-d tree. The fourth algorithm is instead based on the voxelization method used in a software product for computational neurobiologists. This study shows that the space-partitioning data structures are ideal for finding all the connections in a neuronal network. The voxelization algorithm has, however, more favourable scalability and could therefore prove to be preferable for brain regions with higher amounts of nerve cells. The findings of this study also indicate that an algorithm that uses a k-d tree is faster than the other three methods. Further research needs however to be done in order to ascertain and comprehend the underlying causes.