PIC matrices: A computationally tractable class of probabilistic query operators

Warren R. Greiff, W. Bruce Croft, Howard Turtle

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The inference network model of information retrieval allows for a probabilistic interpretation of query operators. In particular, Boolean query operators are conveniently modeled as link matrices of the Bayesian Network. Prior work has shown, however, that these operators do not perform as well as the the pnorm operators used for modeling query operators in the context of the vector space model. This motivates the search for alternative probabilistic formulations for these operators. The design of such alternatives must contend with the issue of computational tractability, since the evaluation of an arbitrary operator requires exponential time. We define a flexible class of link matrices that are natural candidates for the implementation of query operators and an O(n2) algorithm (n = the number of parent nodes) for the computation of probabilities involving link matrices of this class. We present experimental results indicating that Boolean operators implemented in terms of link matrices from this class perform as well as pnorm operators in the context of the INQUERY inference network.

Original languageEnglish (US)
Pages (from-to)367-405
Number of pages39
JournalACM Transactions on Information Systems
Volume17
Issue number4
DOIs
StatePublished - Oct 1999

Keywords

  • Algorithms
  • Bayesian Networks
  • Boolean queries
  • Computational complexity
  • H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval - Query formulation
  • Inference networks
  • Link matrices
  • Performance
  • Piecewise linear functions
  • Pnorm
  • Theory

ASJC Scopus subject areas

  • Information Systems
  • Business, Management and Accounting(all)
  • Computer Science Applications

Fingerprint Dive into the research topics of 'PIC matrices: A computationally tractable class of probabilistic query operators'. Together they form a unique fingerprint.

Cite this