Indexing Multiple Sets.

@inproceedings{DBLP:conf/vldb/KilgerM94,
  author    = {Christoph Kilger and
               Guido Moerkotte},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {Indexing Multiple Sets},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {180-191},
  ee        = {db/conf/vldb/vldb94-180.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We examine the performance of B+-tree based index structures for multiple sets, as developed in the context of object bases. Index structures for multiple sets can be classified into those that group entries according to their key value and those that group entries according to their set membership. The former are particularly suited for exact match queries on all indexed sets, the latter especially support range queries on a small number of all indexed sets. The goal is to thoroughly evaluate the performance of both grouping strategies.

There exist two good reasons for adding a new index structure to the evaluation:

• The performance potentials of set grouping index structures are not yet fully exploited.
• Up to now, the database administrator has to choose between the key grouping and the set grouping index structures. If the application profile consists of both, exact match queries and range queries, this is not really a choice. Hence, a more flexible index structure is needed which can be tuned to a given mix containing both, exact match and range queries.

These two reasons led us to the development of the CG-tree. The focus of the paper is on introducing the CG-tree and on a thorough analysis of the performance of the CH-index, H-tree, and CG-tree under various conditions.

Copyright © 1994 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

References

[1]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[2]

Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 BibTeX

[3]

Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392 BibTeX

[4]

Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) BibTeX

[5]

Alfons Kemper, Guido Moerkotte: Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice-Hall 1994, ISBN 0-13-629239-9
Contents BibTeX

[6]

...

[7]

...

[8]

Chee Chin Low, Hongjun Lu, Beng Chin Ooi, Jiawei Han: Efficient Access Methods in Deductive and Object-Oriented Databases. DOOD 1991: 68-84 BibTeX

[9]

Chee Chin Low, Beng Chin Ooi, Hongjun Lu: H-trees: A Dynamic Associative Search Index for OODB. SIGMOD Conference 1992: 134-143 BibTeX

[10]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[11]

Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX

[12]

Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX

Referenced by

1. Sven Helmer, Till Westmann, Guido Moerkotte: Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships. VLDB 1998: 98-109
2. Theodore Johnson: Coarse Indices for a Tape-Based Data Warehouse. ICDE 1998: 231-240
3. Janusz Charczuk: Physical Structures Design For Relational Databases. ADBIS 1998: 357-362
4. Thomas A. Mück, Martin L. Polaschek: A Configrable Type Hierarchy Index for OODB. VLDB J. 6(4): 312-332(1997)
5. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
6. Thomas A. Mück, Martin L. Polaschek: The Multikey Type Index for Persistent Object Sets. ICDE 1997: 22-31
7. Thomas A. Mück, Martin L. Polaschek: Optimal Type Hierarchy Linearization for Queries in OODB. DASFAA 1997: 225-234
8. Beng Chin Ooi, Jiawei Han, Hongjun Lu, Kian-Lee Tan: Index Nesting - An Efficient Approach to Indexing in Object-Oriented Databases. VLDB J. 5(3): 215-228(1996)
9. Boris Shidlovsky, Elisa Bertino: A Graph-Theoretic Approach to Indexing in Object-Oriented Databases. ICDE 1996: 230-237
10. Ehud Gudes: A Uniform Indexing Scheme for Object-Oriented Databases. ICDE 1996: 238-246
11. Sridhar Ramaswamy, Paris C. Kanellakis: OODB Indexing by Class-Division. SIGMOD Conference 1995: 139-150
12. Georges Gardarin, Fernando Machuca, Philippe Pucheral: OFL: A Functional Execution Model for Object Query Languages. SIGMOD Conference 1995: 59-70