article

Free access

Evaluation of signature files as set access facilities in OODBs

Authors:

Yoshiharu Ishikawa,

Hiroyuki Kitagawa,

Nobuo OhboAuthors Info & Claims

ACM SIGMOD Record, Volume 22, Issue 2

Pages 247 - 256

https://doi.org/10.1145/170036.170076

Published: 01 June 1993 Publication History

PDF eReader

Abstract

Object-oriented database systems (OODBs) need efficient support for manipulation of complex objects. In particular, support of queries involving evaluations 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 OODBs.

References

[1]

E. Bertino and W. Kim. "Indexing Techniques for Queries on Nested Objects," IEEE Trans. on Knowledge and Data Engineering 1(2):196-214 June 1989.

Digital Library

Google Scholar

[2]

C. Faloutsos and S. Christodoulakis. "Signature Files: An Access Method for Documents and Its Analytical Performance Evaluation," A CM Trans. Database Syst. 2(4):267-288 Oct. 1984.

Digital Library

Google Scholar

[3]

C. Faloutsos. "Access Methods for Text," A GM Comput. Surv. 17(1):49-74 Mar. 1985.

Digital Library

Google Scholar

[4]

C. Faloutsos and S. Christodoulakis. "Description and Performance Analysis of Signature File Methods for Office Filing," A CM Trans. O0#ce Inf. Syst. 5(3):237-257 July 1987.

Digital Library

Google Scholar

[5]

C. Faloutsos and R. Chan. "Fast Text Access Methods for Optical and Large Magnetic Disks: Designs and Performance Comparison," In Proc. o/ l$th VLDB Conf. pp. 280-293 Los Angeles, Calif. 1988.

Digital Library

Google Scholar

[6]

W. Kim, H.-T. Chou, and J. Banerjee. "Operations and Implementation of Complex Objects," IEEE Trans. Softw. Eng. 14(7):985-995 July 1988.

Digital Library

Google Scholar

[7]

W. Kim. Introduction to Object-Oriented DaSabases. The MIT Press, 1990.

Digital Library

Google Scholar

[8]

J. L. Pfaltz, W. :}. Berman, and E. M. Cagley. "Partial-Match Retrieval Using Indexed Descriptor Files," Commun. A CM 23(9):522-528 Sept. 1980.

Digital Library

Google Scholar

[9]

R. Sacks-Davis, A. Kent, and K. Ramamohanarao. "Multikey Access Methods Based on Superimposed Coding Techniques," A CM Trans. Database Syst. 12(4):655-696 Dec. 1987.

Digital Library

Google Scholar

[10]

J. Stein and D. Maier. "Associative Access Support in GemStone,# In K. R. Dittrich, U. Dayal, and A. P. Buchmann, editors, On Object-Oriented Database Systems pp. 323-339. Springer-Verlag, 1991.

Google Scholar

Cited By

View all

Bao TTuan T(2016)Query Optimization in Object Oriented Databases Based on Signature File Hierarchy and SD-TreeContext-Aware Systems and Applications10.1007/978-3-319-29236-6_30(309-321)Online publication date: 17-Apr-2016
https://doi.org/10.1007/978-3-319-29236-6_30
Barranco CHelmer S(2012)An impact ordering approach for indexing fuzzy setsFuzzy Sets and Systems10.1016/j.fss.2011.01.014196(33-46)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1016/j.fss.2011.01.014
Chang YHuang LShen JWang Y(2009)An efficient signature-based strategy for supporting inexact filtering in information filtering systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2008.10.07436:4(8431-8442)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.eswa.2008.10.074
Show More Cited By

Index Terms

Evaluation of signature files as set access facilities in OODBs
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Database management system engines
      1. Database query processing
  2. Information retrieval
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Evaluation of signature files as set access facilities in OODBs
SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of data

Object-oriented database systems (OODBs) need efficient support for manipulation of complex objects. In particular, support of queries involving evaluations of set predicates is often required in handling complex objects. In this paper, we propose a ...
Frame-Sliced Signature Files

A superimposed coding method, frame-sliced signature file, is proposed, and the performance of this method is studied and compared with that of other signature file methods. The response time of the method is improved due to its ability to effectively ...
Inverted files versus signature files for text indexing

Two well-known indexing methods are inverted files and signature files. We have undertaken a detailed comparison of these two approaches in the context of text indexing, paying particular attention to query evaluation speed and space requirements. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGMOD Record Volume 22, Issue 2

June 1, 1993

558 pages

ISSN:0163-5808

DOI:10.1145/170036

Editors:
Peter Buneman
Univ. of Pennsylvania
,
Sushil Jajodia,
Won Kim
UniSQL, Inc., Austin, TX

Issue’s Table of Contents

SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of data
June 1993
566 pages
ISBN:0897915925
DOI:10.1145/170035
Editors:
Peter Buneman
Univ. of Pennsylvania
,
Sushil Jajodia

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Published in SIGMOD Volume 22, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
417
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)13

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bao TTuan T(2016)Query Optimization in Object Oriented Databases Based on Signature File Hierarchy and SD-TreeContext-Aware Systems and Applications10.1007/978-3-319-29236-6_30(309-321)Online publication date: 17-Apr-2016
https://doi.org/10.1007/978-3-319-29236-6_30
Barranco CHelmer S(2012)An impact ordering approach for indexing fuzzy setsFuzzy Sets and Systems10.1016/j.fss.2011.01.014196(33-46)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1016/j.fss.2011.01.014
Chang YHuang LShen JWang Y(2009)An efficient signature-based strategy for supporting inexact filtering in information filtering systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2008.10.07436:4(8431-8442)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.eswa.2008.10.074
Winarko ERoddick J(2008)A Signature-Based Indexing Method for Efficient Content-Based Retrieval of Relative Temporal PatternsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2008.2020:6(825-835)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1109/TKDE.2008.20
Chen Y(2006)On the Signature Tree Construction and AnalysisIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2006.14618:9(1207-1224)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TKDE.2006.146
Chen YChen Y(2006)A new tree inclusion algorithmInformation Processing Letters10.1016/j.ipl.2005.11.02298:6(253-262)Online publication date: Jun-2006
https://doi.org/10.1016/j.ipl.2005.11.022
Chen Y(2006)On the cost of searching signature treesInformation Processing Letters10.1016/j.ipl.2005.10.01599:1(19-26)Online publication date: 16-Jul-2006
https://dl.acm.org/doi/10.1016/j.ipl.2005.10.015
Kemper AMoerkotte G(2003)Object-Oriented Database SystemsHandbook on Data Management in Information Systems10.1007/978-3-540-24742-5_4(78-193)Online publication date: 2003
https://doi.org/10.1007/978-3-540-24742-5_4
Manolopoulos YNanopoulos ATousidou EManolopoulos YNanopoulos ATousidou E(2003)Storage and Querying of Large Web-LogsAdvanced Signature Indexing for Multimedia and Web Applications10.1007/978-1-4419-8636-8_8(169-181)Online publication date: 2003
https://doi.org/10.1007/978-1-4419-8636-8_8
Manolopoulos YNanopoulos ATousidou EManolopoulos YNanopoulos ATousidou E(2003)Retrieving Similar Web-User BehaviorsAdvanced Signature Indexing for Multimedia and Web Applications10.1007/978-1-4419-8636-8_7(139-167)Online publication date: 2003
https://doi.org/10.1007/978-1-4419-8636-8_7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations