Elements of the randomized combinatorial file structure

ABSTRACT

A file structure designed to provide rapid, random access with minimum storage overhead is presented. Storage and retrieval are achieved by direct attribute combination-to-address transformation thereby negating the necessity for large file dictionaries or list-pointer structures. The attribute combination-to-address transformation is conceptually similar to key-to-address transformation techniques, but the transformation is not limited to operations on a single key but operates on the combination of several independent keys (or any subset of the combination) describing an item or request.A storage and retrieval system utilizing the combinatorial file structure is developed. Storage and retrieval results derived from a simulated document library of 4000 items are presented. The new file organization is shown to have marked value with respect to minimum storage overhead and high retrieval speed.

REFERENCES

• 1: J. D. Aron, Information Systems in Perspective, ACM Computing Surveys (CSUR), v.1 n.4, p.213-236, Dec. 1969 [doi>10.1145/356556.356560]
• 2: BECKER, J.; HAYES, R. Information storage and retrieval: tools, elements, theories. Wiley, New York, 1963.
• 3: BOURNE, C. Methods of information handling. Wiley, New York, 1963.
• 4: J. D. Canter , C. E. Donaghey, UPLIFTS—University of Pittsburgh linear file tandem system, Communications of the ACM, v.8 n.9, p.579-582, Sept. 1965 [doi>10.1145/365559.365623]
• 5: CHERRY, C.; ed. Information theory. Butterworth, London, 1961.
• 6: CHEYDLEUR, B.; ed. Colloquium on technical preconditions for retrieval center operations. Spartan Books, Washington, D. C., 1965.
• 7: CHEYDLEUR, B. F. SHIEF: a realizable form of associative memory. American Documentation, 14:1 (January, 1963) 56-57.
• 8: 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]
• 9: B. J. Dzubak , C. R. Warburton, The organization of structured files, Communications of the ACM, v.8 n.7, p.446-452, July 1965 [doi>10.1145/364995.365688]
• 10: FELLER, W. An introduction to probability theory and its applications. Wiley, New York, 1963.
• 11: GARVIN, P.; ed. Natural language and the computer. McGraw-Hill, New York, 1963.
• 12: GHOSH, S.; ABRAHAM C. Application of finite geometry in file organization for records with multiple-valued attributes. IBM Journal of Research and Development, 12:2 (March, 1968) 180-187.
• 13: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 14: GUSTAFSON, R. A randomized combinatorial file structure for storage and retrieval systems. Ph.D. thesis, University of South Carolina, Columbia (December, 1969).
• 15: GUTENMAKHER, L. Electronic information-logic machines. Interscience, New York, 1963.
• 16: HANAN, M.; DALERMO, F. P. An application of coding theory to a file address problem. IBM Journal of Research and Development, 7:2 (April, 1963) 127-129.
• 17: HAYS, D. Introduction to computational linguistics. Elsevier, Amsterdam, 1967.
• 18: 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]
• 19: KENT, A. Textbook on mechanized information retrieval. Interscience, New York, 1962.
• 20: KENT, A.; TAULBEE, O.; eds. Electronic information handling. Spartan Books, New York, 1965.
• 21: KISEDA, J. R.; PETERSEN, H. E.; SEELBACH, W. C.; TEIG, M. A magnetic associative memory. IBM Journal of Research and Development, 5:2 (April, 1961) 106-121.
• 22: KOHNEIM, A. G,; WEISS, B. An occupancy discipline and applications. SIAM Journal on Applied Mathematics, 14:6 (November, 1966) 1266-1274.
• 23: LEFKOVITZ, D. File structures for on-line systems. Lecture notes for ACM Seminar on File Structures. Detroit, 1967.
• 24: LEHMER, D. The machine tools of combinatories. In: E. Beckenbach; ed. Applied Combinatorial Mathematics. Wiley, New York, 1964.
• 25: V. Y. Lum, Multi-attribute retrieval with combined indexes, Communications of the ACM, v.13 n.11, p.660-665, Nov 1970 [doi>10.1145/362790.362794]
• 26: MEADOW, C. Man-machine communication. Wiley, New York, 1970.
• 27: MEADOW, C. The analysis of information systems. Wiley, New York, 1967.
• 28: PETERSON, W. W. Addressing for random-access storage. IBM Journal of Research and Development, 1:2 (April, 1957) 130-146.
• 29: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 30: G. Salton, Data manipulation and programming problems in automatic information retrieval, Communications of the ACM, v.9 n.3, p.204-210, March 1966 [doi>10.1145/365230.365267]
• 31: SCHAY, G.; RAVER, N. A method for key-to-address transformation. IBM Journal of Research and Development, 7:2 (April, 1963) 121-126.
• 32: SCHECTER, G.; ed. Information retrieval: a critical view. Thompson, Washington, D. C. 1967.
• 33: SPIEGEL, J.; WALKER, D.; eds. Information systems sciences: proceeding of the second congress. Spartan Books, Washington, D. C., 1965.
• 34: Michael E. Tarter , Richard A. Kronmal, Non-uniform key distribution and address calculation sorting, Proceedings of the 1966 21st national conference, p.331-337, January 1966 [doi>10.1145/800256.810712]
• 35: Junichi Toyoda , Yoshikazu Tezuka , Yoshiro Kasahara, Analysis of the Address Assignment Problem for Clustered Keys, Journal of the ACM (JACM), v.13 n.4, p.526-532, Oct. 1966 [doi>10.1145/321356.321361]
• 36: VlCKERY, B. On retrieval system theory. Butterworth, London, 1965.
• 37: WALSTON, C. E. Information retrieval. In: F. Alt; M. Rubinoff; eds. Advances in Computers. Academic Press, New York, 1965.

INDEX TERMS

Keywords:
attribute combination-to-address transformation, combinatorial file, data structures, file access method, file organization, file structures, hash-coding, key-to-address transformation, multiple attribute retrieval, storage and retrieval system