Attribute based file organization in a paged memory environment

ABSTRACT

The high cost of page accessing implies a need for for more careful data organization in a paged memory than is typical of most inverted file and similar approaches to multi-key retrieval. This article analyses that cost and proposes a method called multiple key hashing which attempts to minimize it. Since this approach is not always preferable to inversion, a combined method is described. The exact specifications of this combination for a file with given data and traffic characteristics is formulated as a mathematical program. The proposed heuristic solution to this program can often improve on a simple inversion technique by a factor of 2 or 3.

REFERENCES

• 1: Lefkovitz, D. File Structures for On-Line Systems. Spartan Press, Washington, D.C., 1969, pp. 126-129.
• 2: 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]
• 3: Corbato, F.J., and Vyssotsky, V.A. Introduction and overview of the MULTIC system. Proe. AFIPS 1965 FJCC, Vol. 27, AFIPS Press, Montvale, N.J., pp. 185-196.
• 4: Richard A. Gustafson, Elements of the randomized combinatorial file structure, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland [doi>10.1145/511285.511304]
• 5: Rothnie, J.B. The design of generalized data management systems. Unpublished Ph.D. Diss., Dep. of Civil Eng., M.I.T., 1972, pp. 72-89.
• 6: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Management, Theory

Keywords:
file organization, inverted file, multiple key hashing, paging, retrieval algorithm