Algorithms for parsing search queries in systems with inverted file organization

ABSTRACT

In an inverted file system a query is in the form of a Boolean expression of index terms. In response to a query the system accesses the inverted lists corresponding to the index terms, merges them, and selects from the merged list those records that satisfy the search logic. Considered in this paper is the problem of determining a Boolean expression which leads to the minimum total merge time among all Boolean expressions that are equivalent to the expression given in the query. This problem is the same as finding an optimal merge tree among all trees that realize the truth function determined by the Boolean expression in the query. Several algorithms are described which generate optimal merge trees when the sizes of overlaps between different lists are small compared with the length of the lists.

REFERENCES

• 1: 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]
• 2: HsiAo, D., AND PRYWES, N.S. A system to manage an information system, in Proc. FID/ IFIP Joint Conf. on Mechanized Inform. Storage, Retrieval and Dissemination, Rome, 1967, pp. 637-660.
• 3: 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]
• 4: HUFFMAN, D.A. A method for the construction of minimum redundancy codes. Proc. 1RB 40 (1952), 1098-1101.
• 5: Liu, j.W.S. Algorithms for parsing search queries in inverted file document retrieval systems. Tech. Rep. UIUCDCS-R-75-718, Dep. Comptr. Sci., U. of Illinois, Urbana, Ill., Sept. 1975.
• 6: Jane W. S. Liu , J. M. Milner, Probabilistic models of inverted file information retrieval systems, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.25-37, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806179]
• 7: 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]
• 8: MABTIN, L.D. A model for file structure determination for large on-line data files. Proc. FILE 68 Int. Seminar on File Org., Copenhagen, 1968, pp. 793-834.
• 9: PaYw~s, N.S. Man-computer problem solving with multilists. Proc. IEEE 5~, 12 (Dec. 1966), 1788-1801.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design

Keywords:
inverted file systems, merge algorithms, parsing Boolean queries