Manolopoulos / Nanopoulos / Papadopoulos R-Trees: Theory and Applications

1. Auflage 2010
ISBN: 978-1-84628-293-5
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 194 Seiten

Reihe: Advanced Information and Knowledge Processing

Space support in databases poses new challenges in every part of a database management system & the capability of spatial support in the physical layer is considered very important. This has led to the design of spatial access methods to enable the effective & efficient management of spatial objects. R-trees have a simplicity of structure & together with their resemblance to the B-tree, allow developers to incorporate them easily into existing database management systems for the support of spatial query processing. This book provides an extensive survey of the R-tree evolution, studying the applicability of the structure & its variations to efficient query processing, accurate proposed cost models, & implementation issues like concurrency control and parallelism. Written for database researchers, designers & programmers as well as graduate students, this comprehensive monograph will be a welcome addition to the field.

Autoren/Hrsg.

Manolopoulos, Yannis

Nanopoulos, Alexandros

Papadopoulos, Apostolos N.

Theodoridis, Yannis

Inhaltsverzeichnis

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