Thumbnail
Access Restriction
Subscribed

Author Lum, V. Y.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Balanced filing scheme ♦ Inverted files ♦ Elimination of false drops ♦ Combining indexes ♦ Query ♦ Secondary index files ♦ Multi-attribute retrieval ♦ Secondary keys ♦ Access method ♦ Information retrieval ♦ File organization ♦ Data management ♦ Rapid retrieval ♦ Storage with buckets
Abstract In this paper a file organization scheme designed to replace the use of the popular secondary index filing scheme (or inverted files on secondary key fields) is described. Through the use of redundancy and storing keys (or access numbers of the records) that satisfy different combinations of secondary index values in “buckets,” it is possible to retrieve all keys satisfying any input query derived from a subset of fields by a single access to an index file, although each bucket may be used for many combinations of values and a combination of buckets may be required for a given query.The method which, in its degenerate case, becomes the conventional secondary index filing scheme works similarly but has the following advantages: (1) the elimination of multiple accesses in many cases; (2) the elimination of false drops; (3) the elimination of computer time to perform intersection of key sets each qualified for one secondary index field only; and (4) the avoidance of long strings of keys when an index field appearing in a query has very few possible values. Redundancy, in some cases, is the same as the secondary indexing method. In the general case, trade-off between the number of accesses for query and redundancy exists.
Description Affiliation: IBM Research Lab, San Jose, CA (Lum, V. Y.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 13
Issue Number 11
Page Count 6
Starting Page 660
Ending Page 665


Open content in new tab

   Open content in new tab
Source: ACM Digital Library