R-Trees: Theory and Applications

Title Page

Copyright Page

Dedication Page

Preface

Book Organization

Intended Audience

How to Study This Book

Acknowledgments

Table of Contents

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