Generalized Search Trees for Database Systems.
Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573@inproceedings{DBLP:conf/vldb/HellersteinNP95,
author = {Joseph M. Hellerstein and
Jeffrey F. Naughton and
Avi Pfeffer},
editor = {Umeshwar Dayal and
Peter M. D. Gray and
Shojiro Nishio},
title = {Generalized Search Trees for Database Systems},
booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
publisher = {Morgan Kaufmann},
year = {1995},
isbn = {1-55860-379-4},
pages = {562-573},
ee = {db/conf/vldb/HellersteinNP95.html},
crossref = {DBLP:conf/vldb/95},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
This paper introduces the Generalized Search Tree (GiST), an index structure supporting an extensible set of queries and data types.
The GiST allows new data types to be indexed in a manner supporting queries natural to the types; this is in contrast to previous work on tree extensibility which only supported the traditional set of equality and range predicates.
In a single data structure, the GiST provides all the basic search tree logic required by a database system, thereby unifying disparate structures such as B+-trees and R-trees in a single piece of code, and opening the application of search trees to general extensibility.
To illustrate the flexibility of the GiST, we provide simple method implementations that allow it to behave like a B+-tree, an R-tree, and an RD-tree, a new index for data with set-valued attributes.
We also present a preliminary performance analysis of RD-trees, which leads to discussion on the nature of tree indices and how they behave for various datasets.
Copyright © 1995 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.):
VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland.
Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents
Software
GiST software
References
- [Aok91]
- Paul M. Aoki:
Implementation of Extended Indexes in POSTGRES.
SIGIR Forum 25(1): 2-9(1991)
![bibliographical record in XML](../../xml.gif)
- [BKSS90]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331
![bibliographical record in XML](../../xml.gif)
- [BKSS94]
- Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
Multi-Step Processing of Spatial Joins.
SIGMOD Conference 1994: 197-208
![bibliographical record in XML](../../xml.gif)
- [CDF+94]
- Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling:
Shoring Up Persistent Applications.
SIGMOD Conference 1994: 383-394
![bibliographical record in XML](../../xml.gif)
- [CDG+90]
- ...
- [Com79]
- Douglas Comer:
The Ubiquitous B-Tree.
ACM Comput. Surv. 11(2): 121-137(1979)
![bibliographical record in XML](../../xml.gif)
- [FB74]
- Raphael A. Finkel, Jon Louis Bentley:
Quad Trees: A Data Structure for Retrieval on Composite Keys.
Acta Inf. 4: 1-9(1974)
![bibliographical record in XML](../../xml.gif)
- [FK94]
- Christos Faloutsos, Ibrahim Kamel:
Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.
PODS 1994: 4-13
![bibliographical record in XML](../../xml.gif)
- [Gro94]
- ...
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
![bibliographical record in XML](../../xml.gif)
- [HNP95]
- ...
- [HP94]
- ...
- [HS93]
- Joseph M. Hellerstein, Michael Stonebraker:
Predicate Migration: Optimizing Queries with Expensive Predicates.
SIGMOD Conference 1993: 267-276
![bibliographical record in XML](../../xml.gif)
- [Ill94]
- ...
- [Jag90]
- H. V. Jagadish:
Linear Clustering of Objects with Multiple Atributes.
SIGMOD Conference 1990: 332-342
![bibliographical record in XML](../../xml.gif)
- [KB95]
- Marcel Kornacker, Douglas Banks:
High-Concurrency Locking in R-Trees.
VLDB 1995: 134-145
![bibliographical record in XML](../../xml.gif)
- [KG94]
- ...
- [KKD89]
- Won Kim, Kyung-Chang Kim, Alfred G. Dale:
Indexing Techniques for Object-Oriented Databases.
Object-Oriented Concepts, Databases, and Applications 1989: 371-394
![bibliographical record in XML](../../xml.gif)
- [Knu73]
- Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
![bibliographical record in XML](../../xml.gif)
- [LJF94]
- King-Ip Lin, H. V. Jagadish, Christos Faloutsos:
The TV-Tree: An Index Structure for High-Dimensional Data.
VLDB J. 3(4): 517-542(1994)
![bibliographical record in XML](../../xml.gif)
- [LS90]
- David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
ACM Trans. Database Syst. 15(4): 625-658(1990)
![bibliographical record in XML](../../xml.gif)
- [LY81]
- Philip L. Lehman, S. Bing Yao:
Efficient Locking for Concurrent Operations on B-Trees.
ACM Trans. Database Syst. 6(4): 650-670(1981)
![bibliographical record in XML](../../xml.gif)
- [MCD94]
- Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux:
V-Trees - A Storage Method for Long Vector Data.
VLDB 1994: 321-330
![bibliographical record in XML](../../xml.gif)
- [PSTW93]
- Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer:
Towards an Analysis of Range Query Performance in Spatial Data Structures.
PODS 1993: 214-221
![bibliographical record in XML](../../xml.gif)
- [PTSE95]
- Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer:
Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees.
SIGMOD Conference 1995: 92-103
![bibliographical record in XML](../../xml.gif)
- [Rob81]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18
![bibliographical record in XML](../../xml.gif)
- [SRF87]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518
![bibliographical record in XML](../../xml.gif)
- [Sto86]
- Michael Stonebraker:
Inclusion of New Types in Relational Data Base Systems.
ICDE 1986: 262-269
![bibliographical record in XML](../../xml.gif)
- [WE80]
- C. K. Wong, Malcolm C. Easton:
An Efficient Method for Weighted Sampling Without Replacement.
SIAM J. Comput. 9(1): 111-113(1980)
![bibliographical record in XML](../../xml.gif)
Copyright © Fri Mar 12 17:22:54 2010
by Michael Ley (ley@uni-trier.de)