Show simple item record

dc.contributor.authorKamel, Ibrahimen_US
dc.contributor.authorFaloutsos, Christosen_US
dc.date.accessioned2007-05-23T09:53:34Z
dc.date.available2007-05-23T09:53:34Z
dc.date.issued1993en_US
dc.identifier.urihttp://hdl.handle.net/1903/5366
dc.description.abstractWe propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to impose a linear ordering on the data rectangles. This ordering has to be 'good', in the sense that it should cluster 'similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Among the orderings we tried, the '2D-c' method, the one that uses the (2d) hilbert value of the center of the rectangles, gives the best results.<P>For a static database, the proposed ordering achieves superior packing, outperforming older packing methods [25], and the best dynamic method (R*-trees [3]). The savings are as high as 36% on real data.<P>more importantly, we introduce a dynamic variation, the Hilbert R- tree: : Given the ordering, every node has a well- defined set of sibling nodes; thus, we can deploy the deferred splitting algorithms of the B* -trees. By adjusting the split policy, the Hilbert R-tree can achieve as high utilization as desired. We show that a '3-to-4' split policy achieves good results, consistently outperforming the R* -trees, with up to 28% savings on real data.en_US
dc.format.extent924327 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1993-19en_US
dc.subjectdatabasesen_US
dc.subjectdata structuresen_US
dc.subjectsystems integrationen_US
dc.titleHilbert R-Tree: An Improved R-Tree Using Fractalsen_US
dc.typeTechnical Reporten_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record