Load Balancing and Accelerating Parallel Spatial Join Operations Using Bitmap Indexing

Spatial data arises in a variety of contexts, including Geographical Information Systems (GIS), scientific simulations, and medical applications. With growing size of spatial data, there is an increasing emphasis on efficiently parallelizing spatial join algorithms. In this paper, we show how existing parallel spatial join algorithms suffer from load imbalance problem. Next, we describe an effective approach for load balancing that is based on using bitmaps as a summary structure of the data. We also use bitmaps to speedup in-memory sequential processing. The specific algorithms we have developed are Bitmap Partitioning Spatial Join (BPSJ), where the main ideas is to perform effective load balancing using bitmaps, and In-memory Bitmap-based Spatial Join (IBSJ), which uses bitmaps for efficient spatial join filtering step. Both algorithms have been compared against existing methods. Parallel BPSJ algorithm outperforms parallel well-known PBSM method by an average of 6.1x while IBSJ has an average speed-up of 4.2 times over plane-sweep and 3.06 times over the R-tree method.