Title

Distribution independent spatial data structures and algorithms with applications

Date of Award

6-2000

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Srinivas Aluru

Keywords

Spatial data structures, Fast multipoles, Tree accumulations, Compressed octree

Subject Categories

Computer Sciences | Theory and Algorithms

Abstract

Representation and manipulation techniques for multidimensional point data are essential to numerous applications in areas such as scientific computing, databases, and computational geometry. The main drawback of many current techniques is that the size of the representation and the run-time of manipulation algorithms depend on the distribution of the points, making them unbounded for arbitrary distributions. In this dissertation, we introduce innovative distribution-independent representation and manipulation methods that lead to improvements in application performance.

In many applications, multidimensional points are organized using hyperoctrees because of their uniform hierarchical subdivision and the ability to focus on application specific subsets of data. However, hyperoctrees are distribution-dependent; both their size and efficiency of search and dynamic operations are seriously affected by the distribution.

We propose a novel data structure called Distribution Independent Adaptive Tree (DIAT tree) to resolve the well-known shortcomings, known for almost two decades, of hyperoctrees. We present efficient and distribution-independent algorithms for construction of DIAT trees and simple searches and dynamic operations on DIAT trees. Furthermore, the run-time of our algorithms are linear in the number of dimensions. This is a significant step towards removing the curse of dimensionality. which refers to the exponential dependence on dimension exhibited by many algorithms.

Using DIAT trees, we developed algorithms for access patterns such as all-nearest neighbor queries and spherical region queries, encountered in many applications. With the support of DIAT trees and these algorithms, we believe that distribution-independent algorithms can be designed for many applications. As evidence, we provide an optimal distribution-independent algorithm for the Fast Multipole Method (FMM).

Parallel computation of the FMM is also of interest because FMM is a computationally intensive application. However, it has been impossible to analyze run-times of parallel FMM algorithms because distribution-dependent heuristic methods are thought to be necessary for ensuring proper data decomposition and load balancing. Using parallel DIAT trees, we developed the first provably good, distribution-independent parallel algorithm for the FMM on distributed memory parallel computers. Our algorithm does not require any dynamic data decomposition or explicit load balancing.

To facilitate the invention of the aforementioned algorithms, we introduce two supplementary techniques which are of interest by themselves because of their various applications. Firstly, we provide a simple and distribution-independent technique to map multidimensional points to one dimension through the use of proximity-preserving space-filling curves. Secondly, we present distributed memory algorithms for upward and downward tree accumulations.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=727949281&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS