Megan Thomas and Kirby Zhang and Jimmy Shih and Joseph M. Hellerstein

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-00-1098

, 2000

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/CSD-00-1098.pdf

We present two new techniques for improving the performance of multidimensional indexes. For static data sets, we find that bulk loading techniques are effective at clustering data items in the index; however, traditional designs of an index's bounding predicates can lead to poor performance. We develop and implement in GiST three new bounding predicates, two of which have much better performance characteristics for our Blobworld image-search application than several traditional access methods. We then proceed to study dynamic data sets, the analysis of which lead to a focus on insertion algorithms. We develop, implement, and analyze an insertion algorithm called the Aggressive Insertion Policy, which uses global rather than greedy information when making insertion decisions.

---

BibTeX citation:

@techreport{Thomas:CSD-00-1098,
    Author= {Thomas, Megan and Zhang, Kirby and Shih, Jimmy and Hellerstein, Joseph M.},
    Title= {Bounding Predicates and Insertion Policies for Multidimensional Indexes},
    Year= {2000},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/5674.html},
    Number= {UCB/CSD-00-1098},
    Abstract= {We present two new techniques for improving the performance of multidimensional indexes. For static data sets, we find that bulk loading techniques are effective at clustering data items in the index; however, traditional designs of an index's bounding predicates can lead to poor performance. We develop and implement in GiST three new bounding predicates, two of which have much better performance characteristics for our Blobworld image-search application than several traditional access methods. We then proceed to study dynamic data sets, the analysis of which lead to a focus on insertion algorithms. We develop, implement, and analyze an insertion algorithm called the Aggressive Insertion Policy, which uses global rather than greedy information when making insertion decisions.},
}

EndNote citation:

%0 Report
%A Thomas, Megan 
%A Zhang, Kirby 
%A Shih, Jimmy 
%A Hellerstein, Joseph M. 
%T Bounding Predicates and Insertion Policies for Multidimensional Indexes
%I EECS Department, University of California, Berkeley
%D 2000
%@ UCB/CSD-00-1098
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/5674.html
%F Thomas:CSD-00-1098