Bernd-Uwe Pagel
ABSTRACT
In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket accesses needed to perform a window query. Our analytical approach exhibits the performance phenomena independent of data structure and implementation details and whether the objects are points or non-point objects.
- 1.N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. A CM SIGMOD Int. Conf. on Management of Data, Atlantic City, 1990. Google Scholar
Digital Library
- 2.M.W. Freeston. The BANG file: a new kind of grid file. In Proc. A CM SIGMOD Int. Conf. on the Management of Data, pages 260-169, San Francisco, 1987. Google ScholarDigital Library
- 3.O. Giinther. Efficient structures for geometric data management, volume 337 of Lecture Notes in Computer Science. Springer, Berlin, 1988. Google ScholarDigital Library
- 4.A. Guttman. R-trees: a dynamic index structure for spatial searching, in Proc. A CM SIGMOD lnt. Conf. on Management of Data, pages 47-57, Boston, 1984. Google ScholarDigital Library
- 5.A. Henrich, H.-W. Six, and P. Widmayer. The LSD- tree" spatial access to multidimensional point- and non-point objects. In 15th Int. Conf. on VLDB, pages 45-53, Amsterdam, 1989. Google ScholarDigital Library
- 6.A. Hutflesz, H.-W. Six, and P. Widmayer. The R-file: an efficient access structure for proximity queries. In Proc. 6th Int. Conf. on Data Engineering, pages 372-379, Los Angeles, 1990. Google ScholarDigital Library
- 7.J. Nievergelt, H. Hinterberger, and K.C. Sevcik. The grid file: an adaptable, symmetric multikey file structure. A CM Transactions on Database Systems, 9(1):3S-71, 1984. Google ScholarDigital Library
- 8.B. Seeger and H.-P. Kriegel. The buddy-tree: an efficient and robust access method for spatial data base systems. In 16th Int. Conf. on VLDB, pages 590-601, Brisbane, 1990. Google ScholarDigital Library
Index Terms
- Towards an analysis of range query performance in spatial data structures
Recommendations
On the efficiency of multiple range query processing in multidimensional data structures
IDEAS '13: Proceedings of the 17th International Database Engineering & Applications SymposiumMultidimensional data are commonly utilized in many application areas like electronic shopping, cartography and many others. These data structures support various types of queries, e.g. point or range query. The range query retrieves all tuples of a ...
Spatial data warehouses and spatial OLAP come towards the cloud: design and performance
Cloud computing systems handle large volumes of data by using almost unlimited computational resources, while spatial data warehouses (SDWs) are multidimensional databases that store huge volumes of both spatial data and conventional data. Cloud ...
Improving range-sum query evaluation on data cubes via polynomial approximation
Inefficient query answering is the main drawback in Decision Support Systems (DSS), due to the very large size of the multidimensional data stored in the underlying Data Warehouse Server (DWS). Aggregate queries are the most frequent and useful kind for ...
Comments