Accession Number:

ADA350392

Title:

Accurate Modeling of Region Data

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1998-04-01

Pagination or Media Count:

22.0

Abstract:

Spatial data appear in numerous applications, such as GIS multimedia and even traditional databases. Most of the analysis has focused on point data, typically using the uniformity assumption, or, more accurately, a fractal distribution. However, no results exist for non-point spatial data, like 2-d regions e.g., islands, 3-d volumes e.g., physical objects in the real world etc. 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.

Subject Categories:

  • Theoretical Mathematics
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE