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

• Published in 1994
• Added on 2010-08-31

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

• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.9180&rep=rep1&type=pdf

Other information

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-10},
	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
}