Extended Boolean model

The Extended Boolean Model was introduced in 1983 by Gerard Salton, Edward A. Fox, Harry Wu. The goal of the Extended Boolean Model is to overcome the drawbacks of Boolean model used in information retrieval. The Boolean model doesn't consider term weight while doing query, and the result set of a boolean query is often either too small or too big. The idea of the extended model is to make use of partial matching and term weight as in the vector space model. It combines the characteristics of the Vector Space Model with the properties of Boolean algebra and ranks the similarity between queries and documents.

Definitions

In the Extended Boolean model, a document is represented as a vector (similarly to in the vector model). Each dimension corresponds to a separate term weight associated with the document.

The weight of term K_x associated with document d_j can be defined as:

$w_{x,j}=f_{x,j}*{\frac {Idf_{x}}{max_{i}Idf_{x}}}$

where Idf_x is inverse document frequency.

The weight vector associated with document d_j can be represented as:

$\mathbf {v} _{d_{j}}=[w_{1,j},w_{2,j},\ldots ,w_{i,j}]$

The 2 Dimensions Example

Figure 1: The similarities of q = (K_x ∨ K_y) and document d_j, d_j+1.

Figure 2: The similarities of q = (K_x ∧ K_y) and document d_j, d_j+1.

Considering the space composed of two terms K_x and K_y only, the corresponding term weights are w₁ and w₂. Thus, for query q_or = (K_x ∨ K_y), we can calculate the similarity with the following formula:

$sim(q_{or},d)={\sqrt {\frac {w_{1}^{2}+w_{2}^{2}}{2}}}$

For query q_and = (K_x ∧ K_y), we can use:

$sim(q_{and},d)=1-{\sqrt {\frac {(1-w_{1})^{2}+(1-w_{2})^{2}}{2}}}$

Generalizing the idea and P-norms

We can generalize the previous 2D extended boolean model example to higher t-dimension of Euclidean distances.

This can be done using P-norms which extend the notion of distance to include p-distances, where 1 ≤ p ≤ ∞ is a new parameter.

• A generalized conjunctive query is given by:

$q_{or}=k_{1}\lor ^{p}k_{2}\lor ^{p}....\lor ^{p}k_{t}$

• The similarity of $q_{or}$ and $d_{j}$ can be define:

$sim(q_{or},d_{j})={\sqrt[{p}]{\frac {w_{1}^{p}+w_{2}^{p}+....+w_{t}^{p}}{t}}}$

• A generalized disjunctive query is given by:

$q_{and}=k_{1}\land ^{p}k_{2}\land ^{p}....\land ^{p}k_{t}$

• The similarity of $q_{and}$ and $d_{j}$ can be define:

$sim(q_{and},d_{j})=1-{\sqrt[{p}]{\frac {(1-w_{1})^{p}+(1-w_{2})^{p}+....+(1-w_{t})^{p}}{t}}}$

Examples

Consider the query q = (K₁ ∧ K₂) ∨ K₃, The similarity between query q and document d can be the following formula:

$sim(q,d)={\sqrt[{p}]{\frac {(1-{\sqrt[{p}]{({\frac {(1-w_{1})^{p}+(1-w_{2})^{p}}{2}}}}))^{p}+w_{3}^{p}}{2}}}$

Further reading

• Adaptive Feedback Methods in an Extended Boolean Model by Dr.Jongpill Choi
• Interpolation of the extended Boolean retrieval model

See also

• Information retrieval

References

• Dr. E. Garcia, The Extended Boolean Model - Weighted Queries: Term Weights, p-Norm Queries and Multiconcept Types. Boolean OR Extended? AND that is the Query