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

• Published in 1994
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.

## Other information

key
Kamel1994
type
article
2010-08-31
date_published
1994-09-14
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.},
}