R-Trees: Theory and Applications (eBook)

Title Page 3
Copyright Page 4
Dedication Page 5
Preface 6
Book Organization 6
Intended Audience 7
How to Study This Book 8
Acknowledgments 8
Table of Contents 9
List of Figures 13
List of Tables 16
Part I FUNDAMENTAL CONCEPTS 17
1. Introduction 18
1.1 The Original R-tree 22
1.2 Summary 28
2. Dynamic Versions of R-trees 29
2.1 The R+-tree 29
2.2 The R*-tree 32
2.3 The Hilbert R-tree 34
2.4 Linear Node Splitting 36
2.5 Optimal Node Splitting 38
2.6 Branch Grafting 39
2.7 Compact R-trees 41
2.8 cR-trees 41
2.9 Deviating Variations 43
2.9.1 PR-trees 44
2.9.2 LR-trees 45
2.10 Summary 48
3. Static Versions of R-trees 49
3.1 The Packed R-tree 49
3.2 The Hilbert Packed R-tree 50
3.3 The STR R-tree 51
3.4 Top-Down Packing Techniques 52
3.5 Small-Tree-Large-Tree and GBI 54
3.6 Bulk Insertion by Seeded Clustering 56
3.7 The Buffer R-tree 58
3.8 R-tree with Low Stabbing Number 59
3.9 Merging R-trees 59
3.10 Summary 61
Part II QUERY PROCESSING ISSUES 63
4. Fundamental Query Processing Techniques 64
4.1 Two-step Processing 64
4.2 Range and Topological Queries 66
4.3 Nearest-Neighbor Queries 68
4.3.1 A Branch-and-Bound Algorithm 69
4.3.2 An Improvement to the Original Algorithm 71
4.3.3 Incremental Nearest-Neighbor Searching 72
4.3.4 Comparison of Nearest Neighbor Algorithms 74
4.4 Spatial Join Queries 75
4.4.1 Algorithm Based on Depth-First Traversal 75
4.4.2 Algorithm Based on Breadth-First Traversal 78
4.4.3 Join Between an R-tree-Indexed and a Non-Indexed Dataset 80
4.5 Summary 81
5. Processing More Complex Queries 82
5.1 Categorical Range Queries 82
5.2 Reverse and Constrained Nearest-Neighbor Queries 85
5.2.1 Reverse Nearest Neighbors 85
5.2.2 Generalized Constrained Nearest Neighbor Searching 88
5.3 Multi-way Spatial Join Queries 90
5.4 Incremental Distance-Join and Closest-Pair Queries 93
5.4.1 Incremental Distance Join 93
5.4.2 Distance Semi-Join Query 96
5.4.3 Finding Closest Pairs 96
5.5 All Nearest-Neighbor Queries 98
5.6 Approximate Query Processing on R-trees 100
5.7 Classification of R-tree-Based Query Processing Algorithms 106
5.8 Summary 107
Part III R-TREES IN MODERN APPLICATIONS 109
6. R-trees in Spatiotemporal Databases 110
6.1 Preliminaries 110
6.2 The RT-tree 112
6.3 The 3D R-tree 112
6.4 The 2+3 R-tree 113
6.5 The Historical R-tree 114
6.6 The RST-tree 115
6.7 The Partially Persistent R-tree 116
6.8 The MV3R-tree 117
6.9 The TB-tree 119
6.10 Scalable and Efficient Trajectory Index (SETI) 120
6.11 The Q+R-tree 121
6.12 The FNR-tree and the MON-tree 122
6.13 The Time-Parameterized R-tree 123
6.14 The VCI R-tree 125
6.15 Summary 126
7. R-trees for Multimedia, Warehousing and Mining 127
7.1 R-trees in Multimedia Databases 127
7.1.1 Generic Multimedia Indexing (GEMINI) 127
7.1.2 High-Dimensional Access Methods 131
7.1.3 R-trees and Hidden Markov Models in Music Retrieval 135
7.1.4 R-trees and Self-Organizing Maps 136
7.2 R-trees in Data Warehousing and Data Mining 136
7.3 Summary 140
Part IV ADVANCED ISSUES 141
8. Query Optimization Issues 142
8.1 Selectivity and Cost Models for Selection Queries 142
8.1.1 Formulae for Range Queries 142
8.1.2 Formulae for Nearest-Neighbor Queries 149
8.2 Selectivity and Cost Models for Join Queries 151
8.2.1 Formulae for Pair-Wise Joins 151
8.2.2 Formulae for Multiway Joins 153
8.2.3 Formulae for Distance-Join Queries 155
8.3 Spatiotemporal Query Optimization 156
8.4 Sampling and Histogram-Based Techniques 158
8.5 Summary 159
9. Implementation Issues 160
9.1 Parallel Systems 160
9.1.1 Multidisk Systems 161
9.1.2 Multiprocessor Systems 165
9.2 Concurrency Control 168
9.2.1 R-link Method 169
9.2.2 Top-down Approaches 170
9.3 Issues in Relational Implementations 171
9.3.1 Stochastic Driven Relational R-trees 171
9.3.2 Lazy Deletion Methods 173
9.3.3 R-trees in Research Prototypes 174
9.3.4 R-trees in Commercial Database Systems 178
9.4 Summary 180
Epilogue 181
References 183
Index 198