Bounding Predicates and Insertion Policies for Multidimensional Indexes

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

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-00-1098
May 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},
    Institution = {EECS Department, University of California, Berkeley},
    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