Probabilistic models of inverted file information retrieval systems

ABSTRACT

In this paper, we study several probabilistic models of inverted file information retrieval systems. In particular, the portion of the system which performs the tasks of list accessing and merging is modeled. The average response times of the system for three different methods of managing the disk access and merge processor queues are discussed.

REFERENCES

• 1: Hsiao, D. and Prywes, N. S., "A System to Manage an Information System," in Proc of the FID/IFIP Joint Conference on Mechanized Information Storage, Retrieval and Dissemination, Rome, Italy, 1967.
• 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: Martin, L. D., "A Model for File Structure Determination for Large On-Line Data Files," in Proc of the FILE 68 International Seminar on File Organization, Copenhagen, 1968.
• 4: Prywes, N. S., "Man-Computer Problem Solving with Multilists," Proc. IEEE 54, 12, December, 1966.
• 5: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 6: Thomas C. Lowe, The Influence of Data Base Characteristics and Usage on Direct Access File Organization, Journal of the ACM (JACM), v.15 n.4, p.535-548, Oct. 1968 [doi>10.1145/321479.321482]
• 7: Stellhorn, W. H., "A Specialized Computer for Information Retrieval,"# Report No. UIUCDCS-R-74-637, Department of Computer Science, University of Illinois at Urbana-Champaign, 1974.
• 8: Hollaar, L. A., "A List Merging Processor for Inverted File Information Retrieval Systems," Report No. UIUCDCS-R-75-762, Department of Computer Science, University of Illinois at Urbana-Champaign, 1975.
• 9: Hurley, B. J. and Lawrie, D. H., "A Study of Machine Architectures for Specialized Information Retrieval Computers," presented at Second Workshop on Computer Architecture for Non-Numeric Processing, Gainsville, Florida, January, 1976.
• 10: Feller, W., An Introduction to Probability Theory and Its Applications, 3rd Edition, John Wiley and Sons, Inc., pp. 320-322.
• 11: Kleinrock, L., "Analysis of Time-shared Processor," Naval Res. Logist. Quart. 11, 10, pp. 59-73 (1964).
• 12: Adiri, I. and Avi-Itzhak, B., "A Time-Sharing Queue," Manag. Sci. 15, 11, pp. 639-657 (1969).
• 13: Leonard Kleinrock, Time-shared Systems: a theoretical treatment, Journal of the ACM (JACM), v.14 n.2, p.242-261, April 1967 [doi>10.1145/321386.321388]
• 14: Liu, Jane W. S., "Probabilistic Models of Inverted File Information Retrieval Systems," Technical Report UIUCDCS-R-75-742, Department of Computer Science, University of Illinois at Urbana-Champaign, 1976.
• 15: Kuri Morales, A., "Two Server Models of Inverted File Document Retrieval Systems," Report No. UIUCDCS-R-76-781, Department of Computer Science, University of Illinois at Urbana-Champaign, February, 1976.
• 16: Igal Adiri, A Dynamic Time-Sharing Priority Queue, Journal of the ACM (JACM), v.18 n.4, p.603-610, Oct. 1971 [doi>10.1145/321662.321675]
• 17: Jair M. Babad, A Generalized Multi-Entrance Time-Sharing Priority Queue, Journal of the ACM (JACM), v.22 n.2, p.231-247, April 1975 [doi>10.1145/321879.321886]
• 18: Schrage, L. E., "The Queue M/G/1 with Feedback to Lower Priority Queues," Manag. Sci., Vol. 13, pp. 466-474 (1967).
• 19: Milner, J. M. and Liu, J. W. S., "Secondary Storage Access Scheduling for a Multiuser Inverted File Processing System" presented at Special Interest Conference in the Theory and Applications of Scheduling at Orlando, Florida, February, 1976.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Theory