| Multimedia and spatial database management systems support applications such as geographic information systems, computer-aided design, image search and an increasing variety of other applications. Database management systems make use of search-tree access methods, such as R-trees, as tools to help improve the efficiency of queries. This thesis focuses on improving access method I/O performance by applying insights gained from rigorous performance analysis.; We began work for this thesis by exploring the empirical analysis of access method I/O performance using the performance metrics developed for the access method analysis tool, amdb. We used the results of our access method analysis to develop a customized access method for the image retrieval system called Blobworld.; Employing the amdb access method analysis tool, we analyzed three multidimensional access methods from the research literature in the context of the Blobworld application. Based upon this analysis, we proposed several variants of the R-tree [26], tailored to address the problems discovered during the analysis. We implemented the access methods we proposed in the Generalized Search Trees (GiST) framework and then analyzed them using amdb. Our experiments found that two of the new access methods have better performance characteristics for the Blobworld application than the multidimensional access methods from the literature which we examined.; We enlarged upon the ideas developed during our experiences with Blobworld to develop ideas for improving the performance of search tree access methods in any application. We explored creating richer, more accurate descriptors for data and storing the richer, but larger, descriptors in the free space frequently found on search-tree access method inner nodes, whenever such space is available.; More precisely, we formed subtree descriptors, which we call bounding predicates, based on simple boolean combinations of standard descriptors such as rectangles. Since the problem of choosing these boolean bounding predicates is NP-complete, we implemented and tested several heuristics for tuning the bounding predicates on an access method node, to create good Boolean bounding predicates which fit in the free space available. (Abstract shortened by UMI.)... |
