ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Evaluation of Signature Files as Set Access Facilities in OODBs.

Yoshiharu Ishikawa, Hiroyuki Kitagawa, Nobuo Ohbo: Evaluation of Signature Files as Set Access Facilities in OODBs. SIGMOD Conference 1993: 247-256
@inproceedings{DBLP:conf/sigmod/IshikawaKO93,
  author    = {Yoshiharu Ishikawa and
               Hiroyuki Kitagawa and
               Nobuo Ohbo},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Evaluation of Signature Files as Set Access Facilities in OODBs},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {247-256},
  ee        = {http://doi.acm.org/10.1145/170035.170076, db/conf/sigmod/IshikawaKO93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Object-oriented database systems (OODBS) need eficient support for manipulation of complex objects. In particular, support of queries involving evaluation of set predicates is often required in handling complex objects. In this paper, we propose a scheme to apply signature file techniques, which were originally invented for text retrieval, to the support of set value accesses, and quantitatively evaluate their potential capabilities. Two signature file organizations, the sequential signature file and the bit-sliced signature file, are considered and their performance is compared with that of the nested index for queries involving the set inclusion operator (<=). We develop a detailed cost model and present analytical results clarifying their retrieval, storage, and update costs. Our analysis shows that the bit-sliced signature file is a very promising set access facility in 00DBs.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1015 KB]

References

[Bert89]
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX
[Falo84]
Christos Faloutsos, Stavros Christodoulakis: Signature Files: An Access Method for Documents and Its Analytical Performance Evaluation. ACM Trans. Inf. Syst. 2(4): 267-288(1984) BibTeX
[Falo85]
Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985) BibTeX
[Falo87]
Christos Faloutsos, Stavros Christodoulakis: Description and Performance Analysis of Signature File Methods for Office Filing. ACM Trans. Inf. Syst. 5(3): 237-257(1987) BibTeX
[Falo88]
Christos Faloutsos, Raphael Chan: Fast Text Access Methods for Optical and Large Magnetic Disks: Designs and Performance Comparison. VLDB 1988: 280-293 BibTeX
[Kim88]
Won Kim, Hong-Tai Chou, Jay Banerjee: Operations and Implementation of Complex Objects. IEEE Trans. Software Eng. 14(7): 985-996(1988) BibTeX
[Kim90]
...
[Pfal80]
John L. Pfaltz, William J. Berman, Edgar M. Cagley: Partial-Match Retrieval Using Indexed Descriptor Files. Commun. ACM 23(9): 522-528(1980) BibTeX
[SD87]
Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao: Multikey Access Methods Based on Superimposed Coding Techniques. ACM Trans. Database Syst. 12(4): 655-696(1987) BibTeX
[Stei91]
...

Referenced by

  1. Yuping Yang, Mukesh Singhal: Accessing Data Cubes along Complex Dimensions. DOLAP 1999: 73-78
  2. Kjetil Nørvåg: Efficient Use of Signatures in Object-Oriented Database Systems. ADBIS 1999: 367-381
  3. Wang-Chien Lee, Dik Lun Lee: Dictionary: A New Access Method for Query Processing in Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 10(3): 371-388(1998)
  4. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
  5. Hennie J. Steenhagen, Rolf A. de By, Henk M. Blanken: Translating OSQL-Queries into Efficient Set Expressions. EDBT 1996: 183-197
  6. Dimitrios Dervos, P. Linardis, Yannis Manolopoulos: Perfect Encoding: a Signature Method for Text Retrieval. ADBIS 1996: 176-182
  7. Sridhar Ramaswamy, Paris C. Kanellakis: OODB Indexing by Class-Division. SIGMOD Conference 1995: 139-150
  8. Wang-Chien Lee, Dik Lun Lee: Combining Indexing Technique with Path Dictionary for Nested Object Queries. DASFAA 1995: 107-114
  9. Boris Novikov: Towards a Realistic Model of Indices in Object Bases. ADBIS 1995: 281-294
  10. B. Sreenath, S. Seshadri: The hcC-tree: An Efficient Index Structure for Object Oriented Databases. VLDB 1994: 203-213
  11. Boris Novikov: Indices for Set-Theoretical Operations in Object Bases. ADBIS 1994: 208-216
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
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:40:15 2009