R-Trees: Theory and Applications (Advanced Information and Knowledge Processing)

Nowadays, a significant number of applications require the organization of data elements which contain at least one spatial attribute. Space support in databases poses new challenges in every part of a database management system and 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 and efficient management of spatial objects. R-trees have a simplicity of structure and, 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 and its variations to efficient query processing, accurate proposed cost models, and implementation issues like concurrency control and parallelism. Based on the observation that ``space is everywhere", the authors anticipate that we are in the beginning of the era of the ``ubiquitous R-tree" analogous to the way B-trees were considered 25 years ago. Written for database researchers, designers and programmers as well as graduate students, this comprehensive monograph will be a welcome addition to the field. The book successfully integrates research results of the last 20 years, in a clear and highly readable manner. It is the first book dedicated to R-trees and related access methods, and I believe it will be valuable as a reference to everyone interested in the area. Prof. Timos Sellis, National Technical University of Athens Preface......Page 3 Contents......Page 6 Figures......Page 10 Tables......Page 13 Introduction......Page 14 The Original R-tree......Page 18 Summary......Page 24 -tree......Page 25 The R*-tree......Page 28 The Hilbert R-tree......Page 30 Linear Node Splitting......Page 32 Optimal Node Splitting......Page 34 Branch Grafting......Page 35 cR-trees......Page 37 Deviating Variations......Page 39 Summary......Page 44 The Packed R-tree......Page 45 The Hilbert Packed R-tree......Page 46 The STR R-tree......Page 47 Top-Down Packing Techniques......Page 48 Small-Tree-Large-Tree and GBI......Page 50 Bulk Insertion by Seeded Clustering......Page 52 The Buffer R-tree......Page 54 Merging R-trees......Page 55 Summary......Page 57 Two-step Processing......Page 59 Range and Topological Queries......Page 61 Nearest-Neighbor Queries......Page 63 Spatial Join Queries......Page 70 Summary......Page 76 Categorical Range Queries......Page 77 Reverse and Constrained Nearest-Neighbor Queries......Page 80 Multi-way Spatial Join Queries......Page 85 Incremental Distance-Join and Closest-Pair Queries......Page 88 All Nearest-Neighbor Queries......Page 93 Approximate Query Processing on R-trees......Page 95 Classification of R-tree-Based Query Processing Algorithms......Page 101 Summary......Page 102 Preliminaries......Page 104 The3DR-tree......Page 106 The 2+3 R-tree......Page 107 The Historical R-tree......Page 108 -tree......Page 109 The Partially Persistent R-tree......Page 110 The MV3R-tree......Page 111 The TB-tree......Page 113 Scalable and Efficient Trajectory Index (SETI)......Page 114 The Q+R-tree......Page 115 The FNR-tree and the MON-tree......Page 116 The Time-Parameterized R-tree......Page 117 The VCI R-tree......Page 119 Summary......Page 120 R-trees in Multimedia Databases......Page 121 R-trees in Data Warehousing and Data Mining......Page 130 Summary......Page 134 Selectivity and Cost Models for Selection Queries......Page 135 Selectivity and Cost Models for Join Queries......Page 144 Spatiotemporal Query Optimization......Page 149 Sampling and Histogram-Based Techniques......Page 151 Summary......Page 152 Parallel Systems......Page 153 Concurrency Control......Page 161 Issues in Relational Implementations......Page 164 Summary......Page 173 Epilogue......Page 174 Refs......Page 176 Index......Page 191

nowadays, A Significant Number Of Applications Require The Organization Of Data Elements Which Contain At Least One Spatial Attribute. Space Support In Databases Poses New Challenges In Every Part Of A Database Management System And 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 And Efficient Management Of Spatial Objects.

r-trees Have A Simplicity Of Structure And, 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 And Its Variations To Efficient Query Processing, Accurate Proposed Cost Models, And Implementation Issues Like Concurrency Control And Parallelism. Based On The Observation That ``space Is Everywhere, The Authors Anticipate That We Are In The Beginning Of The Era Of The ``ubiquitous R-tree Analogous To The Way B-trees Were Considered 25 Years Ago. Written For Database Researchers, Designers And Programmers As Well As Graduate Students, This Comprehensive Monograph Will Be A Welcome Addition To The Field.

the Book Successfully Integrates Research Results Of The Last 20 Years, In A Clear And Highly Readable Manner. It Is The First Book Dedicated To R-trees And Related Access Methods, And I Believe It Will Be Valuable As A Reference To Everyone Interested In The Area.

prof. Timos Sellis, National Technical University Of Athens