IEEE Transactions on Knowledge and Data Engineering · 2000 · 118 citations · 42 references
ComputingComputer ScienceData ManagementData StructuresDatabasesQuery OptimizationQuery ProcessingSpatial Data StructuresSpatial Database SystemsSpatial DatabasesAnalytical ModelsCost ModelsDatabase Management SystemsJoinR-treesSpatial JoinsSpatial Query ProcessingTree Structures
Selection and join queries are fundamental operations in database management systems (DBMS). Support for nontraditional data, including spatial objects, in an efficient manner is of ongoing interest in database research. Toward this goal, access methods and cost models for spatial queries are necessary tools for spatial query processing and optimization. We present analytical models that estimate the cost (in terms of node and disk accesses) of selection and join queries using R-tree-based structures. The proposed formulae need no knowledge of the underlying R-tree structure(s) and are applicable to uniform-like and nonuniform data distributions. In addition, experimental results are presented which show the accuracy of the analytical estimations when compared to actual runs on both synthetic and real data sets.
42
Maintaining knowledge about temporal intervals
James F. Allen · Communications of the ACM · 1983 · 7.5K citations · Full text
A relational model of data for large shared data banks
E. F. Codd · Communications of the ACM · 1983 · 4.8K citations
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations