|
|
|
 |
|
 |
|
I/O Complexity for Range Queries on Region Data Stored Using an R-tree
|
G. Proietti and
C. Faloutsos
View Paper (PDF)
Return to Session 19: Index Schemas II
In this paper we study the node distribution of an R-tree storing region data, like for instance islands, lakes or human-inhabited areas. We will show that real region datasets are packed in minimum bounding rectangles (MBRs) whose area distribution follows the same power law, named REGAL (REGion Area Law), as that for the regions themselves. Moreover, these MBRs are packed in their turn into MBRs following the same law, and so on iteratively, up to the root of the R-tree. Based on this observation, we are able to accurately estimate the search effort for range queries, the most prominent spatial operation, using a small number of easy-to-retrieve parameters. Experiments on a variety of real datasets (islands, lakes, human-inhabited areas) show that our estimation is accurate, enjoying a maximum geometric average relative error within 30%.
Copyright(C) 2000 ACM
|
|
|
|
|
|
|
