The hcC-tree: An Efficient Index Structure for Object Oriented Databases.
B. Sreenath, S. Seshadri:
The hcC-tree: An Efficient Index Structure for Object Oriented Databases.
VLDB 1994: 203-213@inproceedings{DBLP:conf/vldb/SreenathS94,
author = {B. Sreenath and
S. Seshadri},
editor = {Jorge B. Bocca and
Matthias Jarke and
Carlo Zaniolo},
title = {The hcC-tree: An Efficient Index Structure for Object Oriented
Databases},
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 = {203-213},
ee = {db/conf/vldb/vldb94-203.html},
crossref = {DBLP:conf/vldb/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Object oriented database systems, in contrast to traditional relational
database systems, allow the scope of a query against a class to be
either the class itself or all classes in the class hierarchy rooted at
the class. If object oriented databases have to achieve acceptable
performance levels against such queries, we need indexes that support
efficient retrieval of instances from a single class as well as from
all the classes in a class hierarchy. In this paper, we propose a new
index structure called hcC-tree (hierarchy class Chain tree) that
supports both kinds of retrieval efficiently. Moreover, the update
cost of the index structure is bounded by the height of the hcC-tree
(which is usually never more than four). We have implemented hcC-trees
along with H-trees and CH-trees (two other index structures that have
been proposed in the literature) and report a detailed performance
analysis of the three structures. The performance study reveals that
hcC-trees perform much better than the other two structures under most
circumstances. The balanced behaviour of hcC-tree under all kinds of
queries and in the presence of updates shows that it is a promising
index structure for the future.
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
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.):
VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile.
Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX
References
- [BK89]
- Elisa Bertino, Won Kim:
Indexing Techniques for Queries on Nested Objects.
IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX
- [Com79]
- Douglas Comer:
The Ubiquitous B-Tree.
ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
- [IKO93]
- Yoshiharu Ishikawa, Hiroyuki Kitagawa, Nobuo Ohbo:
Evaluation of Signature Files as Set Access Facilities in OODBs.
SIGMOD Conference 1993: 247-256 BibTeX
- [KKD89]
- ...
- [KM90]
- Alfons Kemper, Guido Moerkotte:
Access Support in Object Bases.
SIGMOD Conference 1990: 364-374 BibTeX
- [LLOH91]
- Chee Chin Low, Hongjun Lu, Beng Chin Ooi, Jiawei Han:
Efficient Access Methods in Deductive and Object-Oriented Databases.
DOOD 1991: 68-84 BibTeX
- [LOL92]
- Chee Chin Low, Beng Chin Ooi, Hongjun Lu:
H-trees: A Dynamic Associative Search Index for OODB.
SIGMOD Conference 1992: 134-143 BibTeX
Referenced by
- Thomas A. Mück, Martin L. Polaschek:
A Configrable Type Hierarchy Index for OODB.
VLDB J. 6(4): 312-332(1997)
- Elisa Bertino, Paola Foscoli:
On Modeling Cost Functions for Object-Oriented Databases.
IEEE Trans. Knowl. Data Eng. 9(3): 500-508(1997)
- Thomas A. Mück, Martin L. Polaschek:
The Multikey Type Index for Persistent Object Sets.
ICDE 1997: 22-31
- Chee Yong Chan, Cheng Hian Goh, Beng Chin Ooi:
Indexing OODB Instances based on Access Proximity.
ICDE 1997: 14-21
- Thomas A. Mück, Martin L. Polaschek:
Optimal Type Hierarchy Linearization for Queries in OODB.
DASFAA 1997: 225-234
- 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)
- Sridhar Ramaswamy, Paris C. Kanellakis:
OODB Indexing by Class-Division.
SIGMOD Conference 1995: 139-150
- Georges Gardarin, Fernando Machuca, Philippe Pucheral:
OFL: A Functional Execution Model for Object Query Languages.
SIGMOD Conference 1995: 59-70
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:01 2009