Algorithms for Parsing Search Queries in Systems with Inverted File Organization.

Jane W.-S. Liu: Algorithms for Parsing Search Queries in Systems with Inverted File Organization. ACM Trans. Database Syst. 1(4): 299-316(1976)

@article{DBLP:journals/tods/Liu76,
  author    = {Jane W.-S. Liu},
  title     = {Algorithms for Parsing Search Queries in Systems with Inverted
               File Organization},
  journal   = {ACM Trans. Database Syst.},
  volume    = {1},
  number    = {4},
  year      = {1976},
  pages     = {299-316},
  ee        = {http://doi.acm.org/10.1145/320493.320490, db/journals/tods/Liu76.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

Copyright © 1976 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

References

[1]: Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[2]: ...
[3]: ...
[4]: ...
[5]: ...
[6]: ...
[7]: Thomas C. Lowe: The Influence of Data Base Characteristics and Usage on Direct Access File Organization. J. ACM 15(4): 535-548(1968) BibTeX
[8]: ...
[9]: ...

Referenced by

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]