Packed R-trees Using Fractals

dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorKamel, Ibrahimen_US
dc.date.accessioned2004-05-31T22:22:56Z
dc.date.available2004-05-31T22:22:56Z
dc.date.created1992-12en_US
dc.date.issued1998-10-15en_US
dc.description.abstractWe 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.extent508568 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/578
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3009en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-92-133en_US
dc.titlePacked R-trees Using Fractalsen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
CS-TR-3009.ps
Size:
496.65 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3009.pdf
Size:
268.13 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3009.ps