Generalizing "Search" in Generalized Search Trees

Paul M. Aoki

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-97-950

1997

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/Archive/CSD-97-950.pdf

The generalized search tree, or GiST, defines the basic interfaces required to construct a hierarchical access method for database systems. As originally specified, GiSTs only support record selection. In this paper, we show how a small number of additional interfaces enable GiSTs to support a much larger class of search and computation operations. Members of this class, which includes nearest-neighbor and ranked search, user-defined aggregation and index-assisted selectivity estimation, are increasingly common in new database applications. The advantages of implementing these operations in the GiST framework include reduction of user development effort and the ability to use "industrial strength" concurrency and recovery mechanisms provided by expert implementors.

BibTeX citation:

@techreport{Aoki:CSD-97-950,
    Author= {Aoki, Paul M.},
    Title= {Generalizing "Search" in Generalized Search Trees},
    Year= {1997},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5502.html},
    Number= {UCB/CSD-97-950},
    Abstract= {The generalized search tree, or GiST, defines the basic interfaces required to construct a hierarchical access method for database systems. As originally specified, GiSTs only support record selection. In this paper, we show how a small number of additional interfaces enable GiSTs to support a much larger class of search and computation operations. Members of this class, which includes nearest-neighbor and ranked search, user-defined aggregation and index-assisted selectivity estimation, are increasingly common in new database applications. The advantages of implementing these operations in the GiST framework include reduction of user development effort and the ability to use "industrial strength" concurrency and recovery mechanisms provided by expert implementors.},
}

EndNote citation:

%0 Report
%A Aoki, Paul M. 
%T Generalizing "Search" in Generalized Search Trees
%I EECS Department, University of California, Berkeley
%D 1997
%@ UCB/CSD-97-950
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5502.html
%F Aoki:CSD-97-950