On sampling regional data

The region quadtree is a very popular hierarchical data structure for the representation of binary images (regional data) and it is heavily used at the physical level of many spatial databases. Random sampling algorithms obtain approximate answers of aggregate queries on these databases efficiently. In the present report, we examine how four different sampling methods are applied to specific quadtree implementations (to the most widely used linear implementations). In addition, we examine how two probabilistic models (a parametric model of random images and a model of random trees) can be used for analysing the cost of these methods.