Multikey Access Methods Based on Superimposed Coding Techniques

Get BibTex-formatted data

Author

(Abstract File Only),R. Sacks-Davis,A. Kent,K. Ramamohanarao

Entry type

article

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 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.

Date

1987 – December

URL

https://www.cerias.purdue.edu/ ... orts_and_papers/view/1170

Journal

ACM Transactions on Database Systems

Key alpha

acm

Number

Pages

655-696

Volume

Publication Date

2001-01-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ acm,
	title = "Multikey Access Methods Based on Superimposed Coding Techniques",
	author = "(Abstract File Only),R. Sacks-Davis,A. Kent,K. Ramamohanarao",
	year = "1987",
	month = "December",
	journal = "ACM Transactions on Database Systems",
	number = "4",
	pages = "655-696",
	volume = "12",
	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 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.",
	url = "https://www.cerias.purdue.edu/apps/reports_and_papers/view/1170",
}