Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Filters

19931

Settings

Author: search.filters.author.Kamel, IbrahimSubject: search.filters.subject.systems integration

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Hilbert R-Tree: An Improved R-Tree Using Fractals
    (1993) Kamel, Ibrahim; Faloutsos, Christos; ISR
    We 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.

    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.

    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.