Multikey Access Scheme Based on Term Discrimination and Signature Clustering.

Jae-Woo Chang, Yoon-Joon Lee: Multikey Access Scheme Based on Term Discrimination and Signature Clustering. DASFAA 1989: 211-218
  author    = {Jae-Woo Chang and
               Yoon-Joon Lee},
  editor    = {Sukho Lee and
               Hideko S. Kunii and
               Won Kim and
               In Sup Paik and
               Yahiko Kambayashi},
  title     = {Multikey Access Scheme Based on Term Discrimination and Signature
  booktitle = {International Symposium on Database Systems for Advanced Applications,
               Seoul, Korea, April 10-12, 1989},
  publisher = {Dept. of Computer Science, KAIST, P.O. Box 150, ChongRyang, Seoul,
               131-650, Korea},
  year      = {1989},
  pages     = {211-218},
  ee        = {db/conf/dasfaa/ChangL89.html},
  crossref  = {DBLP:conf/dasfaa/89},
  bibsource = {DBLP,}


In order to improve the two-level signature file scheme proposed by Sacks-Davis et al. [19], we propose a new multikey access scheme based on term discrimination and signature clustering. By term discrimination, we create a separate, efficient access method for the terms frequently used in user queries. We in addition cluster similar signatures by means of these terms so that we may achieve good performance on retrieval. Meanwhile we provide the gross spacetime analysis of our scheme and compare it with that of the two-level signature file scheme. We show that our scheme can achieve 20-30% savings in retrieval time. Finally we propose a family of access methods constructed using our scheme.

Copyright © 1989 by The Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. Permission to copy without all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the DASFAA copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. To copy otherwise, or to republish, requires a fee and/or special permission from the Organizing Commitee.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 2, EDBT, ICDT, MFDBS, DASFAA" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX


P. Bruce Berra, Soon Myoung Chung, Nabil I. Hachem: Computer Architecture for a Surrogate File to a Very Large Data/Knowledge Base. IEEE Computer 20(3): 25-32(1987) BibTeX
Stavros Christodoulakis, Christos Faloutsos: Design Considerations for a Message File Server. IEEE Trans. Software Eng. 10(2): 201-210(1984) BibTeX
Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985) BibTeX
Christos Faloutsos: Signature files: Design and Performance Comparison of Some Signature Extraction Methods. SIGMOD Conference 1985: 63-82 BibTeX
Christos Faloutsos, Raphael Chan: Fast Text Access Methods for Optical and Large Magnetic Disks: Designs and Performance Comparison. VLDB 1988: 280-293 BibTeX
Christos Faloutsos, Stavros Christodoulakis: Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies. VLDB 1985: 165-170 BibTeX
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
Roger L. Haskin, Raymond A. Lorie: On Extending the Functions of a Relational Database System. SIGMOD Conference 1982: 207-212 BibTeX
Alan J. Kent, Ron Sacks-Davis, Kotagiri Ramamohanarao: A Superimposed Coding Scheme Based on Multiple Block Descriptor Files for Indexing Very Large Data Bases. VLDB 1988: 351-359 BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
Kotagiri Ramamohanarao, John Shepherd: A Superimposed Codeword Indexing Scheme for Very Large Prolog Databases. ICLP 1986: 569-576 BibTeX
Charles S. Roberts: Partial-Match Via the Method of Superimposed Codes. Proceedings of the IEEE 67(12): 1624-1642(1979) BibTeX
Ron Sacks-Davis, Kotagiri Ramamohanarao: A two level superimposed coding scheme for partial match retrieval. Inf. Syst. 8(4): 273-289(1983) BibTeX
Ron Sacks-Davis: Performance of a multi-key access method based on descriptors and superimposed coding techniques. Inf. Syst. 10(4): 391-403(1985) BibTeX
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
Gerard Salton, Michael McGill: Introduction to Modern Information Retrieval. McGraw-Hill Book Company 1984, ISBN 0-07-054484-0
Michael J. Wise, David M. W. Powers: Indexing Prolog Clauses via Superimposed Code Words and Filed Encoded Words. SLP 1984: 203-210 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:05:13 2009