Given two 4-dimensional minimum bounding rectangle (MBRS) in an R-tree, A =(2, 10; 40, 60; 32, 40; -2, 11) and B = (3, 4; 30, 50; 30, 40; 20, 23), please use anMBR, E to minimally bound both MBRS A and B. E=

R-Trees The R-tree is intended for indexing two (and higher) dimensional objects in terms of their…

Answered: Given two 4-dimensional minimum…

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

Given two 4-dimensional minimum bounding rectangle (MBRS) in an R-tree, A =
(2, 10; 40, 60; 32, 40; -2, 11) and B = (3, 4; 30, 50; 30, 40; 20, 23), please use an
MBR, E to minimally bound both MBRS A and B. E=

Expert Solution

Step 1

R-Trees

The R-tree is intended for indexing two (and higher) dimensional objects in terms of their minimum bounding rectangles (MBR).
Nodes of the tree store MBRs of objects or collections of objects.
The leaf nodes of the R-tree store the exact MBRs or bounding boxes of the individual geometric objects, along with a pointer to the storage location of the contained geometry.
All non-leaf nodes store references to several bounding boxes for each of which is a pointer to a lower level node.
The tree is constructed hierarchically by grouping the leaf boxes into larger, higher level boxes which may themselves be grouped into even larger boxes at the next higher level.
The original boxes are never subdivided, a consequence of this approach is that the non-leaf node ‘covering boxes’ can be expected to overlap each other.

Variations of R-tree

To cope with the overlapping boxes this method was improved, decomposing the space into disjoint cells, which are mapped into buckets.
This method based on disjointness partitions the objects into arbitrary disjoint sub objects and then groups the sub objects in another structure.
This data structure is called R+-tree.
Overlapping of rectangles is avoided by clipping them against each other, creating additional, smaller rectangles.
Each object is associated with all the bounding rectangles that it intersects.
All bounding rectangles in the tree are non-overlapping (with the exception of the bounding rectangles for the objects at the leaf nodes).
The result is that there may be several paths starting at the root to the same object.
This may lead to an increase in the height of the tree. However, retrieval time is sped up.
The R*-treeis a variant of the R-tree which makes use of the most complex of the node splitting algorithms.
The algorithm differs from the other algorithms as it attempts to reduce both overlap and coverage.
In particular, the primary focus is on reducing overlap with ties broken by favoring the splits that reduce the coverage by using the splits that minimize the perimeter of the bounding boxes of the resulting nodes.
In addition, when a node a overflows, instead of immediately splitting A, an attempt is made first to see if some of the objects in A could possibly be more suited to being in another node.
This is achieved by reinserting a fraction (30% has been found to yield good performance) of these objects in the tree (termed forced reinsertion).
The node is only split if it has been found to overflow after reinsertion has taken place.
This method is quite complex.