# Hilbert R-tree: An improved R-tree using fractals

- Published in 1994
- Added on

In the collection

We propose a new \(\mathbb{R}\)-tree structure that outperforms all the older ones. The heart of the idea is to facilitate the deferred splitting approach in \(\mathbb{R}\)-trees. The is done by proposing an ordering on the \(\mathbb{R}\)-tree nodes. This ordering has to be `good', in the sense that it should group `similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Following [19], we have chosen the so-called `"D-c' method, which sorts rectangles according to the Hilbert value of the center of the rectangles. Given the ordering, every node has a well defined set of sibling nodes; thus, we can use deferred splitting. By adjusting the split policy, the Hilbert \(\mathbb{R}\)-tree can achieve as high utilization as desired. To the contrary, the \(\mathbb{R}^{\ast}\)-tree has no control over the space utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the the Hilbert \(\mathbb{R}\)-tree. Our experiments show that the `2-to-3' split policy provides a compromise between the insertion complexity and the search cost, giving up to 28% savings over the \(\mathbb{R}^{\ast}\)-tree on real data.

## Comment

An R-tree is a way of storing data corresponding to points in Euclidean space in a way that makes it easy to find all the elements in a given rectangle. This paper claims to give a version of an R-tree that's better than all the others.

## Links

## Other information

- key
- Kamel1994
- type
- article
- date_added
- 2010-08-31
- date_published
- 1994-04-26
- booktitle
- PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES
- pages
- 500--500
- publisher
- Citeseer
- volume
- 8958546

### BibTeX entry

@article{Kamel1994, key = {Kamel1994}, type = {article}, title = {Hilbert R-tree: An improved R-tree using fractals}, author = {Kamel, Ibrahim and Faloutsos, Christos}, abstract = {We propose a new \(\mathbb{\{}R{\}}\)-tree structure that outperforms all the older ones. The heart of the idea is to facilitate the deferred splitting approach in \(\mathbb{\{}R{\}}\)-trees. The is done by proposing an ordering on the \(\mathbb{\{}R{\}}\)-tree nodes. This ordering has to be `good', in the sense that it should group `similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Following [19], we have chosen the so-called `"D-c' method, which sorts rectangles according to the Hilbert value of the center of the rectangles. Given the ordering, every node has a well defined set of sibling nodes; thus, we can use deferred splitting. By adjusting the split policy, the Hilbert \(\mathbb{\{}R{\}}\)-tree can achieve as high utilization as desired. To the contrary, the \(\mathbb{\{}R{\}}^{\{}\ast{\}}\)-tree has no control over the space utilization, typically achieving up to 70{\%}. We designed the manipulation algorithms in detail, and we did a full implementation of the the Hilbert \(\mathbb{\{}R{\}}\)-tree. Our experiments show that the `2-to-3' split policy provides a compromise between the insertion complexity and the search cost, giving up to 28{\%} savings over the \(\mathbb{\{}R{\}}^{\{}\ast{\}}\)-tree on real data.}, comment = {An R-tree is a way of storing data corresponding to points in Euclidean space in a way that makes it easy to find all the elements in a given rectangle. This paper claims to give a version of an R-tree that's better than all the others.}, date_added = {2010-08-31}, date_published = {1994-04-26}, urls = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.9180{\&}rep=rep1{\&}type=pdf}, collections = {Basically computer science}, url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.9180{\&}rep=rep1{\&}type=pdf}, urldate = {2010-08-31}, year = 1994, booktitle = {PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES}, pages = {500--500}, publisher = {Citeseer}, volume = 8958546 }