Multikey Access Methods Based on Superimposed Coding Techniques.
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)@article{DBLP:journals/tods/Sacks-DavisK87,
author = {Ron Sacks-Davis and
Alan J. Kent and
Kotagiri Ramamohanarao},
title = {Multikey Access Methods Based on Superimposed Coding Techniques},
journal = {ACM Trans. Database Syst.},
volume = {12},
number = {4},
year = {1987},
pages = {655-696},
ee = {http://doi.acm.org/10.1145/32204.32222, db/journals/tods/Sacks-DavisK87.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Both single-level and two-level indexed descriptor schemes for
multikey retrieval are presented and compared. The descriptors
are formed using superimposed coding techniques and stored
using a bit-inversion technique. A fast-batch insertion
algorithm for which the cost of forming the bit-inverted file
is less than one disk access per record is presented. For
large data files, it is shown that the two-level implementation
is generally more efficient for queries with a small number of
matching records. For queries that specify two or more values,
there is a potential problem with the two-level implementation
in that costs may accrue when blocks of records match the
query but individual records within these blocks do not.
One approach to overcoming this problem is to set bits in the
descriptors based on pairs of indexed terms.
This approach is presented and analyzed.
Copyright © 1987 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.
CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [1]
- Alfred V. Aho, Margaret J. Corasick:
Efficient String Matching: An Aid to Bibliographic Search.
Commun. ACM 18(6): 333-340(1975) BibTeX
- [2]
- ...
- [3]
- Burton H. Bloom:
Space/Time Trade-offs in Hash Coding with Allowable Errors.
Commun. ACM 13(7): 422-426(1970) BibTeX
- [4]
- Robert S. Boyer, J. Strother Moore:
A Fast String Searching Algorithm.
Commun. ACM 20(10): 762-772(1977) BibTeX
- [5]
- Stavros Christodoulakis:
Implications of Certain Assumptions in Database Performance Evaluation.
ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
- [6]
- Stavros Christodoulakis, Christos Faloutsos:
Design Considerations for a Message File Server.
IEEE Trans. Software Eng. 10(2): 201-210(1984) BibTeX
- [7]
- Stavros Christodoulakis:
Issues in the Architecture of a Document Archiver using Optical Disk Technology.
SIGMOD Conference 1985: 34-50 BibTeX
- [8]
- ...
- [9]
- ...
- [10]
- Christos Faloutsos:
Access Methods for Text.
ACM Comput. Surv. 17(1): 49-74(1985) BibTeX
- [11]
- Christos Faloutsos:
Signature files: Design and Performance Comparison of Some Signature Extraction Methods.
SIGMOD Conference 1985: 63-82 BibTeX
- [12]
- Christos Faloutsos, Stavros Christodoulakis:
Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies.
VLDB 1985: 165-170 BibTeX
- [13]
- ...
- [14]
- ...
- [15]
- Roger L. Haskin, Raymond A. Lorie:
On Extending the Functions of a Relational Database System.
SIGMOD Conference 1982: 207-212 BibTeX
- [16]
- ...
- [17]
- Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt:
Fast Pattern Matching in Strings.
SIAM J. Comput. 6(2): 323-350(1977) BibTeX
- [18]
- ...
- [19]
- Ian A. Macleod:
A data base management system for document retrieval applications.
Inf. Syst. 6(2): 131-137(1981) BibTeX
- [20]
- John L. Pfaltz, William J. Berman, Edgar M. Cagley:
Partial-Match Retrieval Using Indexed Descriptor Files.
Commun. ACM 23(9): 522-528(1980) BibTeX
- [21]
- ...
- [22]
- Kotagiri Ramamohanarao, John Shepherd:
A Superimposed Codeword Indexing Scheme for Very Large Prolog Databases.
ICLP 1986: 569-576 BibTeX
- [23]
- ...
- [24]
- Ron Sacks-Davis, Kotagiri Ramamohanarao:
A two level superimposed coding scheme for partial match retrieval.
Inf. Syst. 8(4): 273-289(1983) BibTeX
- [25]
- 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
- [26]
- ...
- [27]
- ...
- [28]
- ...
- [29]
- ...
- [30]
- C. J. van Rijsbergen:
Information Retrieval.
Butterworth 1979, ISBN 0-408-70929-4
BibTeX
- [31]
- Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz:
Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula.
Commun. ACM 26(11): 940-944(1983) BibTeX
- [32]
- Harry K. T. Wong, Hsiu-Fen Liu, Frank Olken, Doron Rotem, Linda Wong:
Bit Transposed Files.
VLDB 1985: 448-457 BibTeX
- [33]
- S. Bing Yao:
Approximating the Number of Accesses in Database Organizations.
Commun. ACM 20(4): 260-261(1977) BibTeX
- [34]
- George Kingsley Zipf:
Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology.
Addison-Wesley 1949
BibTeX
Referenced by
- Yuping Yang, Mukesh Singhal:
Accessing Data Cubes along Complex Dimensions.
DOLAP 1999: 73-78
- Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao:
Inverted Files Versus Signature Files for Text Indexing.
ACM Trans. Database Syst. 23(4): 453-490(1998)
- Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao, James A. Thom, Justin Zobel:
Atlas: A Nested Relational Database System for Text Applications.
IEEE Trans. Knowl. Data Eng. 7(3): 454-470(1995)
- Dik Lun Lee, Young Man Kim, Gaurav Patel:
Efficient Signature File Methods for Text Retrieval.
IEEE Trans. Knowl. Data Eng. 7(3): 423-435(1995)
- Sam Yuan Sung, H. Zhang:
Signature False Drops due to Combinatorial Error.
DASFAA 1995: 124-130
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993)
- Yoshiharu Ishikawa, Hiroyuki Kitagawa, Nobuo Ohbo:
Evaluation of Signature Files as Set Access Facilities in OODBs.
SIGMOD Conference 1993: 247-256
- Chun-Wu Roger Leng, Dik Lun Lee:
Optimal Weight Assignment for Signature Generation.
ACM Trans. Database Syst. 17(2): 346-373(1992)
- Zheng Lin, Christos Faloutsos:
Frame-Sliced Signature Files.
IEEE Trans. Knowl. Data Eng. 4(3): 281-289(1992)
- Justin Zobel, Alistair Moffat, Ron Sacks-Davis:
An Efficient Indexing Technique for Full Text Databases.
VLDB 1992: 352-362
- Christos Faloutsos, H. V. Jagadish:
On B-Tree Indices for Skewed Distributions.
VLDB 1992: 363-374
- Justin Zobel, James A. Thom, Ron Sacks-Davis:
Efficiency of Nested Relational Document Database Systems.
VLDB 1991: 91-102
- Dik Lun Lee, Chun-Wu Leng:
A Partitioned Signature File Structure for Multiattribute and Text Retrieval.
ICDE 1990: 389-397
- Walter W. Chang, Hans-Jörg Schek:
A Signature Access Method for the Starburst Database System.
VLDB 1989: 145-153
- Jae-Woo Chang, Yoon-Joon Lee:
Multikey Access Scheme Based on Term Discrimination and Signature Clustering.
DASFAA 1989: 211-218
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:03 2008