to content Main menu Main menu move to sidebar hide Navigation Main page Contents Current events Random article About Wikipedia Contact us Contribute Help Learn to edit Community portal Recent changes Upload file Special pages Search Search Appearance Donate Create account Log in Personal tools Donate Create account Log in Contents move to sidebar hide (Top) 1 Definitions Toggle Definitions subsection 1.1 Formal representation 2 Example 3 Advantages 4 Disadvantages 5 Data structures and algorithms Toggle Data structures and algorithms subsection 5.1 Hash sets 5.2 Signature file 5.3 Inverted file 6 References Toggle the table of contents Boolean model of information retrieval 7 languages Català Deutsch Español Français Italiano 한국어 Türkçe Edit links Article Talk English Read Edit View history Tools Tools move to sidebar hide Actions Read Edit View history General What links here Related changes Upload file Permanent link Page information Cite this page Get shortened URL Switch to legacy parser Print/export Download as PDF Printable version In other projects Wikidata item Appearance move to sidebar hide From Wikipedia, the free encyclopedia Classical information retrieval model This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (June 2018) (Learn how and when to remove this message) The (standard) Boolean model of information retrieval (BIR)[1] is a classical information retrieval (IR) model where documents are retrieved based on whether they satisfy the conditions of a query that uses Boolean logic. As the first and most-adopted information retrieval model,[2] it treats each document as a set of words, or terms. A user's query uses logical operators like AND, OR, and NOT to create a rule for retrieval. The system then returns all documents that match the rule. Definitions [edit] In the Boolean model, documents and queries are represented using concepts from set theory. A document is seen as a simple collection (a set) of terms, and a query is a formal statement (a Boolean expression) that specifies which terms must or must not be present in a retrieved document. An index term (or term) is a keyword that characterizes the content of a document. Terms are the fundamental units of the model. Common, low-information words (called stop words) like "a", "the", and "is" are typically excluded from being used as index terms. A document is represented as a set of index terms. This is a bag-of-words model, meaning the order and frequency of terms in the original document are ignored. For example, a document about Bayes' theorem might be represented simply as the set { Bayes' theorem, probability, decision-making } {\displaystyle \{{\text{Bayes' theorem, probability, decision-making}}\}} . A query is a formal expression of the user's information need, written using index terms and Boolean operators (AND, OR, NOT). The model retrieves every document that is considered a "match" for this logical expression. Formal representation [edit] The model can be defined formally as follows: Let T = { t 1 , t 2 , … , t k } {\displaystyle T=\{t_{1},t_{2},\ldots ,t_{k}\}} be a set of all index terms. A document D j {\displaystyle D_{j}} is any subset of T {\displaystyle T} . A query Q {\displaystyle Q} is a Boolean expression, typically in conjunctive normal form: Q = ( t a ∨ t b ) ∧ ( ¬ t c ∨ t d ) ∧ … {\displaystyle Q=(t_{a}\lor t_{b})\land (\lnot t_{c}\lor t_{d})\land \dots } where t a , t b , ⋯ ∈ T {\displaystyle t_{a},t_{b},\dots \in T} . Retrieval is the process of identifying the set of all documents { D j } {\displaystyle \{D_{j}\}} that satisfy the query Q {\displaystyle Q} . For example, for the simple query Q = t a ∧ t b {\displaystyle Q=t_{a}\land t_{b}} , the system would retrieve all documents whose set of terms contains both t a {\displaystyle t_{a}} and t b {\displaystyle t_{b}} . Example [edit] Let the set of original (real) documents be, for example D = { D 1 , D 2 , D 3 } {\displaystyle D=\{D_{1},\ D_{2},\ D_{3}\}} where D 1 {\textstyle D_{1}} = "Bayes' principle: The principle that, in estimating a parameter, one should initially assume that each possible value has equal probability (a uniform prior distribution)." D 2 {\textstyle D_{2}} = "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." D 3 {\textstyle D_{3}} = "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 T {\textstyle T} of terms be: T = { t 1 = Bayes' principle , t 2 = probability , t 3 = decision-making , t 4 = Bayesian epistemology } {\displaystyle T=\{t_{1}={\text{Bayes' principle}},t_{2}={\text{probability}},t_{3}={\text{decision-making}},t_{4}={\text{Bayesian epistemology}}\}} Then, the set D {\textstyle D} of documents is as follows: D = { D 1 , D 2 , D 3 } {\displaystyle D=\{D_{1},\ D_{2},\ D_{3}\}} where D 1 = { probability , Bayes' principle } D 2 = { probability , decision-making } D 3 = { probability , Bayesian epistemology } {\displaystyle {\begin{aligned}D_{1}&=\{{\text{probability}},\ {\text{Bayes' principle}}\}\\D_{2}&=\{{\text{probability}},\ {\text{decision-making}}\}\\D_{3}&=\{{\text{probability}},\ {\text{Bayesian epistemology}}\}\end{aligned}}} Let the query Q {\textstyle Q} be ("probability" AND "decision-making"): Q = probability ∧ decision-making {\displaystyle Q={\text{probability}}\land {\text{decision-making}}} Then to retrieve the relevant documents: Firstly, the following sets S 1 {\textstyle S_{1}} and S 2 {\textstyle S_{2}} of documents D i {\textstyle D_{i}} are obtained (retrieved): S 1 = { D 1 , D 2 , D 3 } S 2 = { D 2 } {\displaystyle {\begin{aligned}S_{1}&=\{D_{1},\ D_{2},\ D_{3}\}\\S_{2}&=\{D_{2}\}\end{aligned}}} Where S 1 {\displaystyle S_{1}} corresponds to the documents which contain the term "probability" and S 2 {\displaystyle S_{2}} contain the term "decision-making". Finally, the following documents D i {\textstyle D_{i}} are retrieved in response to Q {\textstyle Q} : Q : { D 1 , D 2 , D 3 } ∩ { D 2 } = { D 2 } {\displaystyle Q:\{D_{1},\ D_{2},\ D_{3}\}\ \cap \ \{D_{2}\}\ =\ \{D_{2}\}} Where the query looks for documents that are contained in both sets S {\displaystyle S} using the intersection operator. This means that the original document D 2 {\displaystyle D_{2}} is the answer to Q {\textstyle Q} . If there is more than one document with the same representation (the same subset of index terms t n {\displaystyle t_{n}} ), every such document is retrieved. Such documents are indistinguishable in the BIR (in other words, equivalent). Advantages [edit] Clean formalism Easy to implement Intuitive concept If the resulting document set is either too small or too big, it is directly clear which operators will produce respectively a bigger or smaller set. It gives (expert) users a sense of control over the system. It is immediately clear why a document has been retrieved given a query. Disadvantages [edit] Exact matching may retrieve too few or too many documents Hard to translate a query into a Boolean expression Ineffective for Search-Resistant Concepts[3] 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 algorithms [edit] 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.[4] Hash sets [edit] Main article: feature hashing 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 file [edit] 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.[5][6][7] The signature file approached is used in BitFunnel. Inverted file [edit] Main article: inverted index 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.[5][6] References [edit] ↑ Lancaster, F.W.; Fayen, E.G. (1973), Information Retrieval On-Line, Melville Publishing Co., Los Angeles, California ↑ "Information Retrieval". MIT Press. Retrieved 2023-12-09. ↑ Shokraneh, Farhad (6 August 2024). "Stop searching and you will find it: Search-Resistant Concepts in systematic review searches". BMJ Evidence-Based Medicine: bmjebm–2023–112798. doi:10.1136/bmjebm-2023-112798. ↑ 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. 1 2 Justin Zobel; Alistair Moffat; and Kotagiri Ramamohanarao. "Inverted Files Versus Signature Files for Text Indexing". 1 2 Bob Goodwin; et al. "BitFunnel: Revisiting Signatures for Search". 2017. ↑ 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", 2009 International Conference on Information Management and Engineering, pp. 385–389, doi:10.1109/ICIME.2009.101, ISBN 978-0-7695-3595-1, S2CID 18147603 Retrieved from "https://en.wikipedia.org/w/index.php?title=Boolean_model_of_information_retrieval&oldid=1342659589" Categories: Mathematical modeling Information retrieval techniques Hidden categories: Articles with short description Short description matches Wikidata Wikipedia articles that are too technical from June 2018 All articles that are too technical This page was last edited on 10 March 2026, at 02:54 (UTC). Page was rendered with Parsoid. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. Privacy policy About Wikipedia Disclaimers Contact Wikipedia Legal & safety contacts Code of Conduct Developers Statistics Cookie statement Mobile view Search Search Toggle the table of contents Boolean model of information retrieval 7 languages Add topic