Computer Science Department
School of Computer Science, Carnegie Mellon University
Accurate Modeling of Region Data
Guido Proietti*, Christos Faloutsos
This is exactly the problem we solve in this paper. Based on experimental evidence that real areas and volumes follow a "power law", that we named REGAL (REGion Area Law), we show (a) the theoretical implications of our model and its connection with the ubiquitous fractals and (b) the first of its practical uses, namely the selectivity estimation for range queries. Experiments on a variety of real datasets (islands, lakes, human-inhabited areas) show that our method is extremely accurate, enjoying a maximum relative error ranging from 1 to 5%, versus 30-70% of a naive model that uses the uniformity assumption.
*On leave from Dipartimento di Matematica Pura ed Applicata, University of L'Aquila, Via Vetoio, I-67010, Italy.