Are window queries representative for arbitrary range queries?
- 3 June 1996
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 150-160
- https://doi.org/10.1145/237661.237704
Abstract
In this paper, we characterize the eciency of spatial access structures in terms of the expected number of data bucket accesses needed to perform a range query. We derive performance formulas for various kinds of range queries like intersection, containment, and enclosure queries with dierent geometric shapes. The formulas exhibit that range query performance in general depends on three parameters: the area sum of the data regions, the perimeter sum, and the number of regions. Only the weights of these parameters vary from shape to shape and query type to query type. To a wide extent, our results prove the conjecture that window queries are representative for range queries in general.Keywords
This publication has 7 references indexed in Scilit:
- Window query-optimal clustering of spatial objectsPublished by Association for Computing Machinery (ACM) ,1995
- The SEQUOIA 2000 storage benchmarkPublished by Association for Computing Machinery (ACM) ,1993
- Towards an analysis of range query performance in spatial data structuresPublished by Association for Computing Machinery (ACM) ,1993
- On packing R-treesPublished by Association for Computing Machinery (ACM) ,1993
- The R*-tree: an efficient and robust access method for points and rectanglesPublished by Association for Computing Machinery (ACM) ,1990
- The Grid FileACM Transactions on Database Systems, 1984
- R-treesPublished by Association for Computing Machinery (ACM) ,1984