Retrieval using ordered lists in inverted and multilist files

ABSTRACT

In several file systems, the data in a file is described by constructing lists of records. Each list contains exactly those records for which some property is true. The motivation for constructing and maintaining these lists is to facilitate the processing of retrieval requests -- in many situations only a subset of the file need be searched in order to determine those records from which information is to be retrieved.When each list is ordered (by, for example, the addresses of the records which occur on it) efficient retrieval algorithms may be devised. Specifically, we shall develop retrieval algorithms for inverted files and multilist files. The algorithms can be used to determine exactly those records which occur on a Boolean expression of lists. These algorithms are controlled by a "trace function" which is used iteratively to select the next candidate.

REFERENCES

• 1: George G. Dodd, Elements of Data Management Systems, ACM Computing Surveys (CSUR), v.1 n.2, p.117-133, June 1969 [doi>10.1145/356546.356550]
• 2: Lefkovitz D., File structures for on-line systems, Spartan Books (1969).
• 3: Morgan H. L. and Kennedy S. R., Mathematical models of file processing: survey and classification, Information Sciences Technical Report No. 3, California Institute of Technology (June 1972).
• 4: David Hsiao , Frank Harary, A formal system for information retrieval from files, Communications of the ACM, v.13 n.2, p.67-73, Feb 1970 [doi>10.1145/362007.362015]
• 5: Manola F. and Hsiao D., A model for keyword based file structures and access, NRL Memorandum Report 2544 (January 1973).
• 6: James W. Welch , J. Wesley Graham, Information retrieval in files described using sets, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500093]