Accelerating Spatial Join Operations using Bit-Indices

Antoine, E., Ramamohanarao, K., Shao, J. and Zhang. R.

    Spatial join is a very expensive operation in spatial databases. In this paper, we propose an innovative method for accelerating spatial join operations using Spatial Join Bitmap (SJB) indices. The SJB indices are used to keep track of intersecting entities in the joining data sets. We provide algorithms for con- structing SJB indices and for maintaining the SJB indices when the data sets are updated. We have performed an extensive study using both real and synthetic data sets of various data distributions. The results show that the use of SJB indices produces substantial speedup ranging from 25% to 150% when compared to Filter trees.
Cite as: Antoine, E., Ramamohanarao, K., Shao, J. and Zhang. R. (2011). Accelerating Spatial Join Operations using Bit-Indices. In Proc. Australasian Database Conference (ADC 2011) Perth, Australia. CRPIT, 115. Heng Tao Shen and Yanchun Zhang Eds., ACS. 123-132
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS