Packed R-trees Using Fractals

dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorKamel, Ibrahimen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:53:15Z
dc.date.available2007-05-23T09:53:15Z
dc.date.issued1993en_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 R-tree 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 Roussoupoulos 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 36% improvement in response time over the best know R-tree variant and up to 58% over the older packing algorithm.en_US
dc.format.extent966243 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5348
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1993-1en_US
dc.subjectdatabasesen_US
dc.subjectdata structuresen_US
dc.subjectSystems Integrationen_US
dc.titlePacked R-trees Using Fractalsen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_93-1.pdf
Size:
943.6 KB
Format:
Adobe Portable Document Format