Construction of Parallel K Dimensional Tree in a Distributed Memory System
2015
- 37Usage
Metric Options: CountsSelecting the 1-year or 3-year option will change the metrics count to percentiles, illustrating how an article or review compares to other articles or reviews within the selected time period in the same journal. Selecting the 1-year option compares the metrics against other articles/reviews that were also published in the same calendar year. Selecting the 3-year option compares the metrics against other articles/reviews that were also published in the same calendar year plus the two years prior.
Example: if you select the 1-year option for an article published in 2019 and a metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019. If you select the 3-year option for the same article published in 2019 and the metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019, 2018 and 2017.
Citation Benchmarking is provided by Scopus and SciVal and is different from the metrics context provided by PlumX Metrics.
Example: if you select the 1-year option for an article published in 2019 and a metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019. If you select the 3-year option for the same article published in 2019 and the metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019, 2018 and 2017.
Citation Benchmarking is provided by Scopus and SciVal and is different from the metrics context provided by PlumX Metrics.
Metrics Details
- Usage37
- Downloads29
- Abstract Views8
Thesis / Dissertation Description
k dimensional trees are an important binary space partitioning data structure in computer science. The goal of this study is to build a parallel k dimensional tree in a distributed memory system to organize the problem domain of the renowned astrophysical simulation N Body problem. The N-Body problem states that a bounded system of N particles interact with each other under the influence of gravity and that these particles change their position continuously due to the force acting upon them. It provides an idea on how large scale structures like galaxies and other cosmological structures are formed. The goal of this work is to organize that system of particles into a data structure, a k-d tree that will enable efficient computation of the forces acting on these particles and their new positions in the system. Our program randomly generated initial conditions for N particles, that is their X, Y, Z coordinate as well as their mass. Then these particles were sorted following one axis in order to build the k-d tree. 1 2 We implemented a sequential version of k-d tree building for and performed benchmarking of this program and analyzed it using several methods that provided us with useful insight on how to improve of the running time of the program and we deemed it more efficient to incorporate parallelism. We have designed and implemented the parallel k-d tree in a distributed memory. ,- Since the construction of k-d tree requires the splitting of search space, we have applied two different methods to implement the k-d tree and decompose the problem space among participating processors: a) the parallel median method and b) the parallel sorting method. We tested our program on up to 512 processors and 64 million data points and measured the timing of the parallel program for both methods. The results are promising and show a linear speedup and efficiency for both methods; with the parallel median method showing a 450% speedup time improvement on the construction of parallel k-d tree. We also compared the two methods and the parallel median method outperforms the parallel sorting method for all test cases.
Bibliographic Details
Provide Feedback
Have ideas for a new metric? Would you like to see something else here?Let us know