Efficient Processing of Region_Overlap Queries Using Spatial Bit-Sliced Indexing

摘要

In this paper we present an efficient index structure to access spatial data. The proposed index, called SBS (Spatial Bit-Sliced), is based on Bit-Sliced indexing method. The Bit-Sliced index has proven to be an efficient data structure for indexing one-dimensional data. The Bit-Sliced is an extension of bitmap indexing used to access data elements with high cardinality. Bitmap indexing improves I/O performance as well as storage saving by using single bits instead of multiple bytes of data to indicate a specific value of data. In this paper we present algorithms using SBS for performing one of the well known spatial operators: Overlap. To measure the performance of SBS for doing the above operation, we present analytical as well as experimental studies. For experimental studies, TIGER data files are used.