|
Preface
List of Figures
List of Tables
Part I. FUNDAMENTAL CONCEPTS
1. Introduction
1.1 The Original R-tree
1.2 Summary
2. Dynamic Versions of R-trees
2.1 The R+-tree
2.2 The R*-tree
2.3 The Hilbert R-tree
2.4 Linear Node Splitting
2.5 Optimal Node Splitting
2.6 Branch Grafting
2.7 Compact R-trees
2.8 cR-trees
2.9 Deviating Variations
2.9.1 PR-trees
2.9.2 LR-trees
2.10 Summary
3. Static Versions of R-trees
3.1 The Packed R-tree
3.2 The Hilbert Packed R-tree
3.3 The STR R-tree
3.4 Top-Down Packing Techniques
3.5 Small-Tree-Large-Tree and GBI
3.6 Bulk Insertion by Seeded Clustering
3.7 The Buffer R-tree
3.8 R-tree with Low Stabbing Number
3.9 Merging R-trees
3.10 Summary
Part II. QUERY PROCESSING ISSUES
4. Fundamental Query Processing Techniques
4.1 Two-step Processing
4.2 Range and Topological Queries
4.3 Nearest-Neighbor Queries
4.3.1 A Branch-and-Bound Algorithm
4.3.2 An Improvement to the Original Algorithm
4.3.3 Incremental Nearest-Neighbor Searching
4.3.4 Comparison of Nearest Neighbor Algorithms
4.4 Spatial Join Queries
4.4.1 Algorithm Based on Depth-First Traversal
4.4.2 Algorithm Based on Breadth-First Traversal
4.4.3 Join Between an R-tree-Indexed and a Non-Indexed Dataset
4.5 Summary
|
5. Processing More Complex Queries
5.1 Categorical Range Queries
5.2 Reverse and Constrained Nearest-Neighbor Queries
5.2.1 Reverse Nearest Neighbors
5.2.2 Generalized Constrained Nearest Neighbor Searching
5.3 Multi-way Spatial Join Queries
5.4 Incremental Distance-Join and Closest-Pair Queries
5.4.1 Incremental Distance Join
5.4.2 Distance Semi-Join Query
5.4.3 Finding Closest Pairs
5.5 All Nearest-Neighbor Queries
5.6 Approximate Query Processing on R-trees
5.7 Classification of R-tree-Based Query Processing Algorithms
5.8 Summary
Part III. R-TREES IN MODERN APPLICATIONS
6. R-trees in Spatiotemporal Databases
6.1 Preliminaries
6.2 The RT-tree
6.3 The 3D R-tree
6.4 The 2+3 R-tree
6.5 The Historical R-tree
6.6 The RST-tree
6.7 The Partially Persistent R-tree
6.8 The MV3R-tree
6.9 The TB-tree
6.10 Scalable and Efficient Trajectory Index (SETI)
6.11 The Q+R-tree
6.12 The FNR-tree and the MON-tree
6.13 The Time-Parameterized R-tree
6.14 The VCI R-tree
6.15 Summary
7. R-trees for Multimedia, Warehousing and Mining
7.1 R-trees in Multimedia Databases
7.1.1 Generic Multimedia Indexing (GEMINI)
7.1.2 High-Dimensional Access Methods
7.1.3 R-trees and Hidden Markov Models in Music Retrieval
7.1.4 R-trees and Self-Organizing Maps
7.2 R-trees in Data Warehousing and Data Mining
7.3 Summary
|
Part IV. ADVANCED ISSUES
8. Query Optimization Issues
8.1 Selectivity and Cost Models for Selection Queries
8.1.1 Formulae for Range Queries
8.1.2 Formulae for Nearest-Neighbor Queries
8.2 Selectivity and Cost Models for Join Queries
8.2.1 Formulae for Pair-Wise Joins
8.2.2 Formulae for Multiway Joins
8.2.3 Formulae for Distance-Join Queries
8.3 Spatiotemporal Query Optimization
8.4 Sampling and Histogram-Based Techniques
8.5 Summary
9. Implementation Issues
9.1 Parallel Systems
9.1.1 Multidisk Systems
9.1.2 Multiprocessor Systems
9.2 Concurrency Control
9.2.1 R-link Method
9.2.2 Top-down Approaches
9.3 Issues in Relational Implementations
9.3.1 Stochastic Driven Relational R-trees
9.3.2 Lazy Deletion Methods
9.3.3 R-trees in Research Prototypes
9.3.4 R-trees in Commercial Database Systems
9.4 Summary
Epilogue
References
Index
|
