Multidimensional binary partitions: distributed data structures for spatial partitioning

Abstract

A multidimensional binary partition (MBP) is a data structure determined by a set of points in n -dimensional space. On certain parallel architectures, this data structure can be easily distributed across the processing nodes of the machine and can provide a natural technique for load balancing and partitioning of application problems that depend on a distribution of dynamically changing points in multidimensional space. This paper describes parallel algorithms for generating and using MBPs on a hypercube parallel machine. It is also shown how these distributed data structures allow efficient parallel searches of the data set. The performance of an implementation of these algorithms on an NCUBE hypercube is presented.