Boolean model of information retrieval: Difference between revisions

Revision as of 13:46, 19 January 2014

Revision as of 09:53, 6 March 2014

Line 3:

==Definitions==

The BIR is based on [[Boolean Logiclogic]] and classical [[Setset theory]] in that both the documents to be searched and the user's query are conceived as sets of terms. Retrieval is based on whether or not the documents contain the query terms. Given a finite set

: T = {t1, t2, ..., tj, ..., tm}

of elements called index terms (e.g. words or expressions - which may be [[stemming|stemmed]] - describing or characterising documents such as keywords given for a journal article), a finite set

: D = {D1, ..., Di, ..., Dn}, where Di is an element of the powerset of T

Line 18:

where ti means that the term ti is present in document Di, whereas NON ti means that it is not.

Equivalently, Q can be given in a [[disjunctive normal form]], too. An operation called retrieval, consisting of two steps, is defined as follows:

: 1. The sets Sj of documents are obtained that contain or not term tj (depending on whether Wj=tj or Wj=NON tj) :

Line 26:

: 2. Those documents are retrieved in response to Q which are the result of the corresponding sets operations, i.e. the answer to Q is as follows:

:: UNION ( [[Intersection|INTERSECTION]] Sj)

==Example==

Line 38:

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

O2 = [[Bayes' theorem|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 Subjectivesubjective Expectedexpected Utilityutility. 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.

O3 = 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.

Line 44:

Let the set T of terms be:

T = {t1 = Bayes' Principle, t2 = probability, t3 = decision-making, t4 =

Bayesian Epistemology}

Line 78:

== Advantages ==

* Clean Formalismformalism

* Easy to implement

* Intuitive concept

Line 84:

== Disadvantages ==

* [[String search algorithm|Exact matching]] may retrieve too few or too many documents

* Difficult to rank output, some documents are more important than others

* Hard to translate a query into a Boolean expression

* All terms are equally weighted

* More like ''[[data retrieval]]'' than ''information retrieval''

== Data structures and algorithms ==

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]], [[Hashhash table|hash tables]]s, [[Inverted index|inverted file]] structure, and so on.<ref name="wartik">{{cite book | last = Wartik | first = Steven | title = Information Retrieval Data Structures & Algorithms | chapter=Boolean operations | publisher = Prentice-Hall, Inc. | year = 1992 | isbn = 0-13-463837-9 | url = http://www.scribd.com/doc/13742235/Information-Retrieval-Data-Structures-Algorithms-William-B-Frakes }}</ref>

=== Hash Sets ===

Another possibility is to use Hash[[hash Setsset]]s. Each document is represented by a Hash-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 vectorsvector]]s. On the worst case performance can degrade from O(n) to O(n²). On the average case, the performance slowdown will not be that much worse than bit vectors and the space usage is much more efficient.

== References ==