Performance Analysis of a Binary-Tree-Based Algorithm for Computing Spatial Distance Histograms

The environment is made up of composition of small particles. Hence, particle simulation is an important tool in many scientific and engineering research fields to simulate the real life processes of the environment. Because of the enormous amount of data in such simulations, data management, storage and processing are very challenging tasks. Spatial Distance Histogram (SDH) is one of the most popular queries being used in this field. In this thesis, we are interested in investigating the performance of improvement of an existing algorithm for computing SDH. The algorithm already being used is using a conceptual data structure called density map which is implemented via a quad tree index. An algorithm having density maps implemented via binary tree is proposed in this thesis. After carrying out many experiments and analysis of the data, we figure out that although the binary tree approach seems efficient in earlier stage, it is same as the quad tree approach in terms of time complexity. However, it provides an improvement in computing time by a constant factor for some data inputs. The second part of this thesis is dedicated to an approach that can potentially reduce the computational time to a great extent by taking advantage of regions where data points are uniformly distributed