Estimating how many records qualify for a spatial predicate is crucial when choosing a cost-effective query execution plan, especially in presence of extra non-spatial criteria. The challenge is far bigger with
geospatial data on the Web
, as information is inherently disparate in many sites and effective search should avoid transmission of large datasets. Our idea is that fast, succinct, yet reliable estimates of spatial selectivity could incur significant reduction in query execution costs. Towards this goal, we examine variants of well known spatial indices enhanced with data distribution statistics, essentially building
. We compare these methods in terms of performance and estimation accuracy over real datasets and query workloads of varying range. Our empirical study exhibits their pros and cons and confirms the potential of spatial histograms for optimized search on the Web of Data.