A comparison of different R-tree construction techniques for range queries on neuromorphological data

Abstract: The brain is the most complex organ in the human body, and there are many reasons to study it. One way of studying the brain is through digital simulations. Such simulations typically require large amounts of data on the 3dimensional structure of individual neurons to be stored and processed efficiently. Commonly, such data is stored using data structures for spatial indexing such as R-trees. A typical operation within neuroscience which needs to make use of these data structures is the range query: a search for all elements within a given subvolume of the model. Since these queries are common, it is important they can be made efficiently. The purpose of this study is to compare a selection of construction methods (repeated R'-tree insertion, one-dimensional sorting packing, Sort-Tile-Recursive (STR) packing, Adaptive STR packing, Hilbert/Z-order/Peano curve packing, and binary splitting packing) for R-trees with respect to their performance in terms of building time, query page reads and query execution time. With reconstructions of neurons from the human brain, ten datasets were generated with densities ranging from 5,000 to 50,000 neurons/mm3 in a 300 µm 600 µm 300 µm volume. Range queries were then run on the R-trees constructed from these datasets. The results show that the lowest query times were achieved using STR packing and Adaptive STR packing. The best performing construction techniques in terms of build time were Peano and Z-order curve packing.