R-Trees: Theory and Applications

Cover......Page 1
Advanced Information and Knowledge Processing......Page 2
R-Trees: Theory and Applications......Page 4
9781852339777......Page 5
Dedication Page......Page 6
Book Organization......Page 8
Intended Audience......Page 9
Acknowledgments......Page 10
Table of Contents......Page 12
List of Figures......Page 16
List of Tables......Page 20
Part I - FUNDAMENTAL CONCEPTS......Page 22
1. Introduction......Page 24
1.1 The Original R-tree......Page 28
1.2 Summary......Page 34
2.1 The R+-tree......Page 36
2.2 The R*-tree......Page 39
2.3 The Hilbert R-tree......Page 41
2.4 Linear Node Splitting......Page 43
2.5 Optimal Node Splitting......Page 45
2.6 Branch Grafting......Page 46
2.8 cR-trees......Page 48
2.9 Deviating Variations......Page 50
2.9.1 PR-trees......Page 51
2.9.2 LR-trees......Page 52
2.10 Summary......Page 55
3.1 The Packed R-tree......Page 56
3.2 The Hilbert Packed R-tree......Page 57
3.3 The STR R-tree......Page 58
3.4 Top-Down Packing Techniques......Page 59
3.5 Small-Tree-Large-Tree and GBI......Page 61
3.6 Bulk Insertion by Seeded Clustering......Page 63
3.7 The Buffer R-tree......Page 65
3.9 Merging R-trees......Page 66
3.10 Summary......Page 68
Part II - QUERY PROCESSING ISSUES......Page 70
4.1 Two-step Processing......Page 72
4.2 Range and Topological Queries......Page 74
4.3 Nearest-Neighbor Queries......Page 76
4.3.1 A Branch-and-Bound Algorithm......Page 77
4.3.2 An Improvement to the Original Algorithm......Page 79
4.3.3 Incremental Nearest-Neighbor Searching......Page 80
4.3.4 Comparison of Nearest Neighbor Algorithms......Page 82
4.4.1 Algorithm Based on Depth-First Traversal......Page 83
4.4.2 Algorithm Based on Breadth-First Traversal......Page 86
4.4.3 Join Between an R-tree-Indexed and a Non-Indexed Dataset......Page 88
4.5 Summary......Page 89
5.1 Categorical Range Queries......Page 90
5.2.1 Reverse Nearest Neighbors......Page 93
5.2.2 Generalized Constrained Nearest Neighbor Searching......Page 96
5.3 Multi-way Spatial Join Queries......Page 98
5.4.1 Incremental Distance Join......Page 101
5.4.3 Finding Closest Pairs......Page 104
5.5 All Nearest-Neighbor Queries......Page 106
5.6 Approximate Query Processing on R-trees......Page 108
5.7 Classification of R-tree-Based Query Processing Algorithms......Page 114
5.8 Summary......Page 115
Part III - R-TREES IN MODERN APPLICATIONS......Page 118
6.1 Preliminaries......Page 120
6.3 The 3D R-tree......Page 122
6.4 The 2+3 R-tree......Page 123
6.5 The Historical R-tree......Page 124
6.6 The R^{ST}-tree......Page 125
6.7 The Partially Persistent R-tree......Page 126
6.8 The MV3R-tree......Page 127
6.9 The TB-tree......Page 129
6.10 Scalable and Efficient Trajectory Index (SETI)......Page 130
6.11 The Q+R-tree......Page 131
6.12 The FNR-tree and the MON-tree......Page 132
6.13 The Time-Parameterized R-tree......Page 133
6.14 The VCI R-tree......Page 135
6.15 Summary......Page 136
7.1.1 Generic Multimedia Indexing (GEMINI)......Page 138
7.1.2 High-Dimensional Access Methods......Page 142
7.1.3 R-trees and Hidden Markov Models in Music Retrieval......Page 146
7.2 R-trees in Data Warehousing and Data Mining......Page 147
7.3 Summary......Page 151
Part IV - ADVANCED ISSUES......Page 152
8.1.1 Formulae for Range Queries......Page 154
8.1.2 Formulae for Nearest-Neighbor Queries......Page 161
8.2.1 Formulae for Pair-Wise Joins......Page 163
8.2.2 Formulae for Multiway Joins......Page 165
8.2.3 Formulae for Distance-Join Queries......Page 167
8.3 Spatiotemporal Query Optimization......Page 168
8.4 Sampling and Histogram-Based Techniques......Page 170
8.5 Summary......Page 171
9.1 Parallel Systems......Page 172
9.1.1 Multidisk Systems......Page 173
9.1.2 Multiprocessor Systems......Page 177
9.2 Concurrency Control......Page 180
9.2.1 R-link Method......Page 181
9.2.2 Top-down Approaches......Page 182
9.3.1 Stochastic Driven Relational R-trees......Page 183
9.3.2 Lazy Deletion Methods......Page 185
9.3.3 R-trees in Research Prototypes......Page 186
9.3.4 R-trees in Commercial Database Systems......Page 190
9.4 Summary......Page 192
Epilogue......Page 194
References......Page 196
Index......Page 212