Partial-match retrieval using indexed descriptor files

In this paper we describe a practical method of partial-match retrieval in very large data files. A binary code word, called a descriptor, is associated with each record of the file. These record descriptors are then used to form a derived descriptor for a block of several records, which will serve...

Full description

Saved in:
Bibliographic Details
Published in:Communications of the ACM 1980-09, Vol.23 (9), p.522-528
Main Authors: Pfaltz, John L., Berman, William J., Cagley, Edgar M.
Format: Magazinearticle
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we describe a practical method of partial-match retrieval in very large data files. A binary code word, called a descriptor, is associated with each record of the file. These record descriptors are then used to form a derived descriptor for a block of several records, which will serve as an index for the block as a whole; hence, the name “indexed descriptor files.” First the structure of these files is described and a simple, efficient retrieval algorithm is presented. Then its expected behavior, in terms of storage accesses, is analyzed in detail. Two different file creation procedures are sketched, and a number of ways in which the file organization can be “tuned” to a particular application are suggested.
ISSN:0001-0782
1557-7317
DOI:10.1145/359007.359013