Selectivity estimation of queries not only provides useful information to the query processing optimization but also may give users a preview of processing results. In this paper, we investigate the problem of selectivity estimation in the context of a spatial dataset. Specifically, we focus on the calculation of four relations, contains, contained, overlap and disjoint, between data objects and a query rectangle using Euler-histograms. We first provide a multi-resolution algorithm which can lead to the exact solutions but at the cost of storage space. To conform to a given storage space, we also provide an approximate algorithm based on a hybrid multi-resolution paradigm. Our experiments suggest that our algorithms greatly out-perform the existing techniques. |
| Cite as: Liu, Q., Yuan, Y. and Lin, X. (2003). Multi-resolution Algorithms for Building Spatial Histograms. In Proc. Fourteenth Australasian Database Conference (ADC2003), Adelaide, Australia. CRPIT, 17. Schewe, K.-D. and Zhou, X., Eds. ACS. 145-151. |
 (from crpit.com)
(local if available)
|