Packed R-trees Using Fractals
dc.contributor.author | Faloutsos, Christos | en_US |
dc.contributor.author | Kamel, Ibrahim | en_US |
dc.date.accessioned | 2004-05-31T22:22:56Z | |
dc.date.available | 2004-05-31T22:22:56Z | |
dc.date.created | 1992-12 | en_US |
dc.date.issued | 1998-10-15 | en_US |
dc.description.abstract | We propose a new packing technique for R-trees for static databases. Given a collection of rectangles, we sort them and we build the Rtree bottom-up. There are several ways to sort the rectangles; the innovation of this work is the use of fractals, and specifically the hilbert curve, to achieve better ordering of the rectangles and eventually better packing. We proposed and implemented several variations and performed experiments on synthetic, as well as real data (a TIGER file from the U.S. Bureau of Census). The winning variation ('2D-c') was the one that sorts the rectangles according to the hilbert value of the center. This variation consistently outperforms the R*-trees [3], Guttman's R-trees [13], as well as the packing method of Roussopoulos and Leifker [24]. The performance gain of the our method seems to increase with the skeweness of the data distribution; specifically, on the (highly skewed) TIGER dataset, it achieves up to 38% improvement in response time over the best known R-tree variant and up to 58% over the older packing algorithm. (Also cross-referenced as UMIACS-TR-92-133) | en_US |
dc.format.extent | 508568 bytes | |
dc.format.mimetype | application/postscript | |
dc.identifier.uri | http://hdl.handle.net/1903/578 | |
dc.language.iso | en_US | |
dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3009 | en_US |
dc.relation.ispartofseries | UMIACS; UMIACS-TR-92-133 | en_US |
dc.title | Packed R-trees Using Fractals | en_US |
dc.type | Technical Report | en_US |