Boolean model of information retrieval

  (Redirected from Standard Boolean model)

The (standard) Boolean model of information retrieval (BIR)[1] is a classical information retrieval (IR) model and, at the same time, the first and most-adopted one. It is used by many IR systems to this day.[citation needed] The BIR is based on Boolean logic and classical set theory in that both the documents to be searched and the user's query are conceived as sets of terms (a bag-of-words model). Retrieval is based on whether or not the documents contain the query terms.

DefinitionsEdit

An index term is a word or expression, which may be stemmed, describing or characterizing a document, such as a keyword given for a journal article. Let

 
be the set of all such index terms.

A document is any subset of  . Let

 
be the set of all documents.

A query is a Boolean expression   in normal form:

 
where   is true for   when  . (Equivalently,   could be expressed in disjunctive normal form.)

We seek to find the set of documents that satisfy  . This operation is called retrieval and consists of the following two steps:

1. For each   in  , find the set   of documents that satisfy  :
 
2. Then the set of documents that satisfy Q is given by:
 

ExampleEdit

Let the set of original (real) documents be, for example

 

where

  = "Bayes' principle: The principle that, in estimating a parameter, one should initially assume that each possible value has equal probability (a uniform prior distribution)."

  = "Bayesian decision theory: A mathematical theory of decision-making which presumes utility and probability functions, and according to which the act to be chosen is the Bayes act, i.e. the one with highest subjective expected utility. If one had unlimited time and calculating power with which to make every decision, this procedure would be the best way to make any decision."

  = "Bayesian epistemology: A philosophical theory which holds that the epistemic status of a proposition (i.e. how well proven or well established it is) is best measured by a probability and that the proper way to revise this probability is given by Bayesian conditionalisation or similar procedures. A Bayesian epistemologist would use probability to define, and explore the relationship between, concepts such as epistemic status, support or explanatory power."

Let the set   of terms be:

 

Then, the set   of documents is as follows:

 

where

 

Let the query   be:

 
Then to retrieve the relevant documents:
  1. Firstly, the following sets   and   of documents   are obtained (retrieved):
     
  2. Finally, the following documents   are retrieved in response to  
     

This means that the original document   (corresponding to  ) is the answer to  .

Obviously, if there is more than one document with the same representation, every such document is retrieved. Such documents are indistinguishable in the BIR (in other words, equivalent).

AdvantagesEdit

  • Clean formalism
  • Easy to implement
  • Intuitive concept

DisadvantagesEdit

  • Exact matching may retrieve too few or too many documents
  • Hard to translate a query into a Boolean expression
  • All terms are equally weighted
  • More like data retrieval than information retrieval
  • Retrieval based on binary decision criteria with no notion of partial matching
  • No ranking of the documents is provided (absence of a grading scale)
  • Information need has to be translated into a Boolean expression, which most users find

awkward

  • The Boolean queries formulated by the users are most often too simplistic
  • The model frequently returns either too few or too many documents in response to a user

query

Data structures and algorithmsEdit

From a pure formal mathematical point of view, the BIR is straightforward. From a practical point of view, however, several further problems should be solved that relate to algorithms and data structures, such as, for example, the choice of terms (manual or automatic selection or both), stemming, hash tables, inverted file structure, and so on.[2]

Hash setsEdit

Another possibility is to use hash sets. Each document is represented by a hash table which contains every single term of that document. Since hash table size increases and decreases in real time with the addition and removal of terms, each document will occupy much less space in memory. However, it will have a slowdown in performance because the operations are more complex than with bit vectors. On the worst-case performance can degrade from O(n) to O(n2). On the average case, the performance slowdown will not be that much worse than bit vectors and the space usage is much more efficient.

Signature fileEdit

Each document can be summarized by Bloom filter representing the set of words in that document, stored in a fixed-length bitstring, called a signature. The signature file contains one such superimposed code bitstring for every document in the collection. Each query can also be summarized by a Bloom filter representing the set of words in the query, stored in a bitstring of the same fixed length. The query bitstring is tested against each signature.[3][4][5]

The signature file approached is used in BitFunnel.

Inverted fileEdit

An inverted index file contains two parts: a vocabulary containing all the terms used in the collection, and for each distinct term an inverted index that lists every document that mentions that term.[3][4]

ReferencesEdit

  1. ^ Lancaster, F.W.; Fayen, E.G. (1973), Information Retrieval On-Line, Melville Publishing Co., Los Angeles, California
  2. ^ Wartik, Steven (1992). "Boolean operations". Information Retrieval Data Structures & Algorithms. Prentice-Hall, Inc. ISBN 0-13-463837-9. Archived from the original on 2013-09-28.
  3. ^ a b Justin Zobel; Alistair Moffat; and Kotagiri Ramamohanarao. "Inverted Files Versus Signature Files for Text Indexing".
  4. ^ a b Bob Goodwin; et. al. "BitFunnel: Revisiting Signatures for Search". 2017.
  5. ^ Richard Startin. "Bit-Sliced Signatures and Bloom Filters".
  • Lashkari, A.H.; Mahdavi, F.; Ghomi, V. (2009), A Boolean Model in Information Retrieval for Search Engines, doi:10.1109/ICIME.2009.101