Show simple item record

dc.contributor.authorKamel, Ibrahimen_US
dc.contributor.authorFaloutsos, Christosen_US
dc.date.accessioned2004-05-31T22:23:05Z
dc.date.available2004-05-31T22:23:05Z
dc.date.created1993-02en_US
dc.date.issued1998-10-15en_US
dc.identifier.urihttp://hdl.handle.net/1903/581
dc.description.abstractWe propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to pack rectangles into the Entree nodes according to a linear ordering as opposed to the more complex heuristics used in the R*tree. 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 '2bc' method, the one that uses the (2d) Filbert value of the center of the rectangles, gives the best results. 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. Moreover, we introduce a dynamic variation, the Eilbc7t R-tree: Given the ordering, every node has a well-defined set of sibling nodes; thus, we can use splitting algorithms that are similar to the deferred splitting of the B*-trees. By adjusting the split policy, the Filbert R-tree can achieve as high utilization as desired. To the contrary, the R*-tree has no control over the utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the Filbert R-tree. Our experiments show that a '2-to-3' split policy achieves good results, consistently outperforming the best competitor (R*-trees), with up to 28% savings on real data. (Also cross-referenced as UMIACS-TR-93-12)en_US
dc.format.extent262988 bytes
dc.format.mimetypeapplication/postscript
dc.language.isoen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3032en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-93-12en_US
dc.titleHilbert R-tree: An improved Rtree using fractalsen_US
dc.typeTechnical Reporten_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


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record