Megan Thomas

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-99-1081
1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1081.pdf

We present the design and analysis of a customized access method for the content-based image retrieval system, Blobworld. Using the amdb access method analysis tool, we analyze three existing multidimensional access methods that support nearest neighbor search in the context of the Blobworld application. Based on this analysis, we propose several variants of the R-tree, tailored to address the problems the analysis revealed. We implemented the access methods we propose in the Generalized Search Trees (GiST) framework and analyzed them using amdb, a tool that enables visualization and performance analysis of access methods. We found that two of our access methods have better performance characteristics for the Blobworld application than any of the traditional multi-dimensional access methods we examined. Based on this experience, we draw conclusions for nearest neighbor access method design, and for the task of constructing custom access methods tailored to particular applications. In particular, we found that our "Top X Jagged Bites" bounding predicate performed better than all the other access methods we tested.

BibTeX citation:

@techreport{Thomas:CSD-99-1081,
    Author = {Thomas, Megan},
    Title = {Creating a Customized Access Method for Blobworld},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1999},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5302.html},
    Number = {UCB/CSD-99-1081},
    Abstract = {We present the design and analysis of a customized access method for the content-based image retrieval system, Blobworld. Using the amdb access method analysis tool, we analyze three existing multidimensional access methods that support nearest neighbor search in the context of the Blobworld application. Based on this analysis, we propose several variants of the R-tree, tailored to address the problems the analysis revealed. We implemented the access methods we propose in the Generalized Search Trees (GiST) framework and analyzed them using amdb, a tool that enables visualization and performance analysis of access methods. We found that two of our access methods have better performance characteristics for the Blobworld application than any of the traditional multi-dimensional access methods we examined. Based on this experience, we draw conclusions for nearest neighbor access method design, and for the task of constructing custom access methods tailored to particular applications. In particular, we found that our "Top X Jagged Bites" bounding predicate performed better than all the other access methods we tested.}
}

EndNote citation:

%0 Report
%A Thomas, Megan
%T Creating a Customized Access Method for Blobworld
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1081
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5302.html
%F Thomas:CSD-99-1081