Partial-match retrieval using indexed descriptor files
- 1 September 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 23 (9) , 522-528
- https://doi.org/10.1145/359007.359013
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.Keywords
This publication has 7 references indexed in Scilit:
- Optimal partial-match retrieval when fields are independently specifiedACM Transactions on Database Systems, 1979
- Partial-match retrieval via the method of superimposed codesProceedings of the IEEE, 1979
- A Practical Approach to Selecting Record Access PathsACM Computing Surveys, 1977
- On the use of bit maps for multiple key retrievalACM SIGPLAN Notices, 1976
- Partial-Match Retrieval AlgorithmsSIAM Journal on Computing, 1976
- Analysis and performance of inverted data base structuresCommunications of the ACM, 1975
- AN INFORMATION RETRIEVAL SYSTEM BASED ON SUPERIMPOSED CODINGPublished by Defense Technical Information Center (DTIC) ,1969