Interesting Esoterica

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

Article by Kamel, Ibrahim and Faloutsos, Christos
  • 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

booktitle
PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES
pages
500--500
publisher
Citeseer
volume
8958546

BibTeX entry

@article{Kamel1994,
	title = {Hilbert R-tree: An improved R-tree using fractals},
	author = {Kamel, Ibrahim and Faloutsos, Christos},
	url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.9180{\&}rep=rep1{\&}type=pdf},
	urldate = {2010-08-31},
	year = 1994,
	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.},
	booktitle = {PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES},
	pages = {500--500},
	publisher = {Citeseer},
	volume = 8958546,
	collections = {basically-computer-science}
}