Generalized Search Trees for Database Systems.

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Software

References

[Aok91]

Paul M. Aoki: Implementation of Extended Indexes in POSTGRES. SIGIR Forum 25(1): 2-9(1991) BibTeX

[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 BibTeX

[BKSS94]

Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 BibTeX

[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 BibTeX

[CDG+90]

...

[Com79]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[FB74]

Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX

[FK94]

Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13 BibTeX

[Gro94]

...

[Gut84]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[HNP95]

...

[HP94]

...

[HS93]

Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX

[Ill94]

...

[Jag90]

H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342 BibTeX

[KB95]

Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145 BibTeX

[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 BibTeX

[Knu73]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[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) BibTeX

[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) BibTeX

[LY81]

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX

[MCD94]

Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux: V-Trees - A Storage Method for Long Vector Data. VLDB 1994: 321-330 BibTeX

[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 BibTeX

[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 BibTeX

[Rob81]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

[SRF87]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[Sto86]

Michael Stonebraker: Inclusion of New Types in Relational Data Base Systems. ICDE 1986: 262-269 BibTeX

[WE80]

C. K. Wong, Malcolm C. Easton: An Efficient Method for Weighted Sampling Without Replacement. SIAM J. Comput. 9(1): 111-113(1980) BibTeX

Referenced by

1. Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez: Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000: 331-342
2. Jochen Van den Bercken, Jens-Peter Dittrich, Bernhard Seeger: javax.XXL: A prototype for a Library of Query processing Algorithms. SIGMOD Conference 2000: 588
3. Jochen Van den Bercken, Martin Schneider, Bernhard Seeger: Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins. EDBT 2000: 495-509
4. Marcel Kornacker: High-Performance Extensible Indexing. VLDB 1999: 699-708
5. Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang: High Level Indexing of User-Defined Types. VLDB 1999: 554-564
6. Kaushik Chakrabarti, Sharad Mehrotra: Efficient Concurrency Control in Multidimensional Access Methods. SIGMOD Conference 1999: 25-36
7. Joseph M. Hellerstein, Lisa Hellerstein, George Kollios: On the Generation of 2-Dimensional Index Workloads. ICDT 1999: 113-130
8. Rasa Bliujute, Simonas Saltenis, Giedrius Slivinskas, Christian S. Jensen: Developing a DataBlade for a New Index. ICDE 1999: 314-323
9. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: The Bulk Index Join: A Generic Approach to Processing Non-Equijoins. ICDE 1999: 257
10. Lukas Relly, Heiko Schuldt, Hans-Jörg Schek: Exporting Database Functionality - The CONCERT Way. IEEE Data Eng. Bull. 21(3): 43-51(1998)
11. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
12. Rasa Bliujute, Christian S. Jensen, Simonas Saltenis, Giedrius Slivinskas: R-Tree Based Indexing of Now-Relative Bitemporal Data. VLDB 1998: 345-356
13. Marcel Kornacker, Mehul A. Shah, Joseph M. Hellerstein: amdb: An Access Method Debugging Tool. SIGMOD Conference 1998: 570-571
14. Michael Jaedicke, Bernhard Mitschang: On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS. SIGMOD Conference 1998: 379-389
15. Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51
16. Elias Koutsoupias, David Scot Taylor: Tight Bounds for 2-Dimensional Indexing Schemes. PODS 1998: 52-58
17. Paolo Ciaccia, Marco Patella, Pavel Zezula: A Cost Model for Similarity Queries in Metric Spaces. PODS 1998: 59-68
18. Kaushik Chakrabarti, Sharad Mehrotra: Dynamic Granular Locking Approach to Phantom Protection in R-Trees. ICDE 1998: 446-454
19. Paul M. Aoki: Generalizing ``Search'' in Generalized Search Trees (Extended Abstract). ICDE 1998: 380-389
20. Paolo Ciaccia, Marco Patella, Pavel Zezula: Processing Complex Similarity Queries with Distance-Based Access Methods. EDBT 1998: 9-23
21. Joseph M. Hellerstein: Online Processing Redux. IEEE Data Eng. Bull. 20(3): 20-29(1997)
22. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
23. Stefan Deßloch, Nelson Mendonça Mattos: Integrating SQL Databases with Content-Specific Search Engines. VLDB 1997: 528-537
24. Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435
25. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415
26. Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
27. Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256
28. Esa Falkenroth: Computational Indexes for Time Series. SSDBM 1996: 242-251