Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database

Selectivity estimation for spatial databases is a core scientific problem in query optimization. The exiting spatial histograms violate theintegrity of spatial objects, so it is difficult to precisely calculate the selectivity of spatial data to deduce the histograms of query results. In view of the above problems, we propose a forward cumulative annular bucket histogram, referred to as the cumulative AB histogram. This histogram establishes annular buckets to receive all spatial area objects. Therefore, it maintains the integrity of area objects and achieves better performance on the selectivity estimation and histogram deduction in fine spatial topological query. We discuss some theories of the cumulative AB-histogram in detail and propose selectivity estimation methods for fine topological queries. We take land use data as example to show accuracy of selectivity estimation and discusstopics relevant to the efficiency and scope of applications.