Partial-match retrieval using indexed descriptor files

Abstract

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.