SCS Undergraduate Thesis Topics
|Dongryeol Lee||Alexander Gray, Andrew Moore||New Algorithmic Techniques for Generalized N-Body Problems|
This research examines existing methods and contributes new techniques for solving generalized N-body problems. These problems are characterized by functions of pairs or n-tuples of points in a metric space, and include fundamental problems in computational physics (electromagnetic and cosmological simulations), computational statistics (nonparametric density estimation and n-point correlations), computational geometry (all-nearest-neighbors problem and radial range-searching), database systems, computer graphics, and computer vision. In solving this important class of problems, I hope to provide a unified approach providing performance scalability with respect to the number and the dimensionality of data points and adaptability to arbitrary data distribution.
First, I propose a new fast kernel density estimation algorithm combining two successful approaches in reducing the computational cost involved in nonparametric density estimation: a fully-recursive approach utilizing adaptive hierarchical data structures in computational geometry (dual-tree recursion) and an analytical approach in approximation theory (fast multipole methods). The technique developed here is general enough to be applied to other problems in which fast evaluations of "pair-wise" kernel functions are required. Secondly, our experiments have shown that tree-based N-body algorithms are highly adaptive to any data distribution and offer superior performance over those using other structures such as simple grids. I propose new tree data structures that will speed up the "branch-and-bound" searching involved in tree-based algorithms. In demonstrating the effectiveness of the newly developed techniques, I will provide experimental results against current state-of-the-art algorithms.