Information retrieval
'''Information retrieval''' ('''IR''') is the science of searching for documents, for [[information]] within documents and for [[Metadata (computing)|metadata]] about documents, as well as that of searching [[relational database]]s and the [[World Wide Web]]. There is overlap in the usage of the terms data retrieval, [[document retrieval]], information retrieval, and [[text retrieval]], but each also has its own body of literature, theory, [[Praxis (process)|praxis]] and technologies.  IR is [[interdisciplinary]], based on [[computer science]], [[mathematics]], [[library science]], [[information science]], [[information architecture]], [[cognitive psychology]], [[linguistics]], [[statistics]] and [[physics]].

Automated information retrieval systems are used to reduce what has been called "[[information overload]]". Many universities and [[public library|public libraries]] use IR systems to provide access to books, journals and other documents. Web [[Web search engine|search engine]]s are the most visible [[Information retrieval applications|IR applications]].

== History ==
{{Rquote|right|But do you know that, although I have kept the diary [on a phonograph] for months past, it never once struck me how I was going to find any particular part of it in case I wanted to look it up?|Dr Seward| [[Bram Stoker|Bram Stoker's]] ''[[Dracula]]'',
 1897}}
The idea of using computers to search for relevant pieces of information was popularized in an article ''[[As We May Think]]'' by [[Vannevar Bush]] in 1945.<ref name="Singhal01">{{cite journal | last = Singhal | first = Amit | title = Modern Information Retrieval: A Brief Overview | journal = Bulletin of the IEEE Computer Society Technical Committee on Data Engineering | volume = 24 | issue = 4 | pages = 35–43 | date = 2001 | url = http://singhal.info/ieee2001.pdf}}</ref> First implementations of information retrieval systems were introduced in the 1950s and 1960s. By 1990 several different techniques had been shown to perform well on small text corpora (several thousand documents).<ref name="Singhal01" />

In 1992 the US Department of Defense, along with the [[National Institute of Standards and Technology]] (NIST), cosponsored the [[Text Retrieval Conference]] (TREC) as part of the TIPSTER text program. The aim of this was to look into the information retrieval community by supplying the infrastructure that was needed for evaluation of text retrieval methodologies on a very large text collection. This catalyzed research on methods that [[scalability|scale]] to huge corpora. The introduction of web [[Web search engine|search engine]]s has boosted the need for very large scale retrieval systems even further.

The use of digital methods for storing and retrieving information has led to the phenomenon of [[digital obsolescence]], where a digital resource ceases to be readable because the physical media, the reader required to read the media, the hardware, or the software that runs on it, is no longer available. The information is initially easier to retrieve than if it were on paper, but is then effectively lost.

=== Timeline  ===
* 1890: Hollerith tabulating machines were used to analyze the US census. ([[Herman Hollerith]]).
* 1945: [[Vannevar Bush]]'s ''[[As We May Think]]'' appeared in ''[[Atlantic Monthly]]'' 
* Late 1940s: The US military confronted problems of indexing and retrieval of wartime scientific research documents captured from Germans.
* 1947: [[Hans Peter Luhn]] (research engineer at IBM since 1941) began work on a mechanized, punch card based system for searching chemical compounds.
* 1950: The term "information retrieval" may have been coined by [[Calvin Mooers]].
* 1950s: Growing concern in the US for a "science gap" with the USSR motivated, encouraged funding, and provided a backdrop for mechanized literature searching systems ([[Allen Kent]] et al) and the invention of citation indexing ([[Eugene Garfield]]).  
* 1955: Allen Kent joined [[Case Western Reserve University]], and eventually becomes associate director of the Center for Documentation and Communications Research. That same year, Kent and colleagues publish a paper in American Documentation describing the precision and recall measures, as well as detailing a proposed "framework" for evaluating an IR system, which includes statistical sampling methods for determining the number of relevant documents not retrieved.
* 1958: International Conference on Scientific Information Washington DC included consideration of IR systems as a solution to problems identified. See: Proceedings of the International Conference on Scientific Information, 1958 (National Academy of Sciences, Washington, DC, 1959)
* 1959: Hans Peter Luhn published "Auto-encoding of documents for information retrieval." 
* 1960: Melvin Earl (Bill) Maron and J. L. Kuhns published "On relevance, probabilistic indexing, and information retrieval" in Journal of the ACM 7(3):216-244, July 1960. 
* Early 1960s: [[Gerard Salton]] began work on IR at Harvard, later moved to Cornell. 
* 1962: [[Cyril W. Cleverdon]] published early findings of the Cranfield studies, developing a model for IR system evaluation. See: Cyril W. Cleverdon, "Report on the Testing and Analysis of an Investigation into the Comparative Efficiency of Indexing Systems". Cranfield Coll. of Aeronautics, Cranfield, England, 1962. 
* 1962: Kent published Information Analysis and Retrieval
* 1963: Weinberg report "Science, Government and Information" gave a full articulation of the idea of a "crisis of scientific information."  The report was named after Dr. [[Alvin Weinberg]]. 
* 1963: [[Joseph Becker]] and [[Robert M. Hayes]] published text on information retrieval. Becker, Joseph; Hayes, Robert Mayo. Information storage and retrieval: tools, elements, theories. New York, Wiley (1963). 
* 1964: [[Karen Sp&auml;rck Jones]] finished her thesis at Cambridge, ''Synonymy and Semantic Classification'', and continued work on [[computational linguistics]] as it applies to IR 
* 1964: The [[National Bureau of Standards]] sponsored a symposium titled "Statistical Association Methods for Mechanized Documentation." Several highly significant papers, including G. Salton's first published reference (we believe) to the SMART system. 
* Mid-1960s: National Library of Medicine developed [[MEDLARS]] Medical Literature Analysis and Retrieval System, the first major machine-readable database and batch retrieval system 
* Mid-1960s: Project Intrex at MIT 
* 1965: [[J. C. R. Licklider]] published ''Libraries of the Future'' 
* 1966: [[Don Swanson]] was involved in studies at University of Chicago on Requirements for Future Catalogs 
* 1968: Gerard Salton published ''Automatic Information Organization and Retrieval''. 
* 1968: [[J. W. Sammon]]'s RADC Tech report "Some Mathematics of Information Storage and Retrieval..." outlined the vector model. 
* 1969: Sammon's "A nonlinear mapping for data structure analysis" (IEEE Transactions on Computers) was the first proposal for visualization interface to an IR system. 
* Late 1960s: [[F. W. Lancaster]] completed evaluation studies of the MEDLARS system and published the first edition of his text on information retrieval 
* Early 1970s: first online systems--NLM's AIM-TWX, MEDLINE; Lockheed's Dialog; SDC's ORBIT 
* Early 1970s: [[Theodor Nelson]] promoting concept of [[hypertext]], published Computer Lib/Dream Machines 
* 1971: [[N. Jardine]] and [[C. J. Van Rijsbergen]] published "The use of hierarchic clustering in information retrieval", which articulated the "cluster hypothesis." (Information Storage and Retrieval, 7(5), pp. 217-240, Dec 1971)
*1975: Three highly influential publications by Salton fully articulated his vector processing framework and term discrimination model: 
** A Theory of Indexing  (Society for Industrial and Applied Mathematics) 
** "A theory of term importance in automatic text analysis", (JASIS v. 26) 
** "A vector space model for automatic indexing", (CACM 18:11) 
* 1978: The First [[Association for Computing Machinery|ACM]] [[SIGIR]] conference. 
* 1979: C. J. Van Rijsbergen published ''Information Retrieval'' (Butterworths). Heavy emphasis on probabilistic models. 
* 1980: First international ACM SIGIR conference, joint with British Computer Society IR group in Cambridge 
* 1982: [[Nicholas J. Belkin|Belkin]], Oddy, and Brooks proposed the ASK (Anomalous State of Knowledge) viewpoint for information retrieval. This was an important concept, though their automated analysis tool proved ultimately disappointing. 
* 1983: Salton (and M. McGill) published Introduction to Modern Information Retrieval (McGraw-Hill), with heavy emphasis on vector models. 
* Mid-1980s: Efforts to develop end user versions of commercial IR systems. 
* 1985-1993: Key papers on and experimental systems for visualization interfaces. 
* Work by [[D. B. Crouch]], [[Robert R. Korfhage]], [[M. Chalmers]], [[A. Spoerri]] and others. 
* 1989: First [[World Wide Web]] proposals by [[Tim Berners-Lee]] at [[CERN]]. 
* 1992: First TREC conference. 
* 1997: Publication of [[Robert R. Korfhage|Korfhage]]'s ''Information Storage and Retrieval''<ref name="korfhage97">{{cite book | last = Korfhage | first = Robert R. | title = Information Storage and Retrieval | publisher = Wiley | date = 1997 | pages = 368 pages | isbn = 978-0-471-14338-3 | url = http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471143383,descCd-authorInfo.html }}</ref> with emphasis on visualization and multi-reference point systems. 
* Late 1990s: Web [[Web search engine|search engine]] implementation of many features formerly found only in experimental IR systems

== Overview ==

An information retrieval process begins when a user enters a query into the system. Queries are formal statements of [[information need]]s, for example search strings in web search engines. In information retrieval a query does not uniquely identify a single object in the collection. Instead, several objects may match the query, perhaps with different degrees of [[relevance|relevancy]].

An object is an entity which keeps or stores information in a database. User queries are matched to objects stored in the database. Depending on the [[Information retrieval applications|application]] the data objects may be, for example, text documents, images or videos. Often the documents themselves are not kept or stored directly in the IR system, but are instead represented in the system by document surrogates.

Most IR systems compute a numeric score on how well each object in the database match the query, and rank the objects according to this value. The top ranking objects are then shown to the user. The process may then be iterated if the user wishes to refine the query.

== Performance measures ==
{{main|Precision and Recall}}

Many different measures for evaluating the performance of information retrieval systems have been proposed. The measures require a collection of documents and a query. All common measures described here assume a ground truth notion of relevancy: every document is known to be either relevant or non-relevant to a particular query. In practice queries may be [[ill-posed]] and there may be different shades of relevancy.

=== Precision ===

Precision is the fraction of the documents retrieved that are [[Relevance (information retrieval)|relevant]] to the user's information need.

:<math> \mbox{precision}=\frac{|\{\mbox{relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{retrieved documents}\}|} </math>

In [[binary classification]], precision is analogous to [[positive predictive value]]. Precision takes all retrieved documents into account. It can also be evaluated at a given cut-off rank, considering only the topmost results returned by the system. This measure is called ''precision at n'' or ''P@n''.

Note that the meaning and usage of "precision" in the field of Information Retrieval differs from the definition of [[accuracy and precision]] within other branches of science and technology.

=== Recall === 

Recall is the fraction of the documents that are relevant to the query that are successfully retrieved.

:<math>\mbox{recall}=\frac{|\{\mbox{relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{relevant documents}\}|} </math>

In binary classification, recall is called [[sensitivity (tests)|sensitivity]]. So it can be looked at as ''the probability that a relevant document is retrieved by the query''.

It is trivial to achieve recall of 100% by returning all documents in response to any query. Therefore recall alone is not enough but one needs to measure the number of non-relevant documents also, for example by computing the precision.

=== Fall-Out ===
The proportion of non-relevant documents that are retrieved, out of all non-relevant documents available:

:<math> \mbox{fall-out}=\frac{|\{\mbox{non-relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{non-relevant documents}\}|} </math>

In binary classification, fall-out is closely related to [[specificity (tests)|specificity]]. More precisely: <math>\mbox{fall-out}=1-\mbox{specificity}</math>. It can be looked at as ''the probability that a non-relevant document is retrieved by the query''.

It is trivial to achieve fall-out of 0% by returning zero documents in response to any query.

=== F-measure === 
{{main|F-score}}
The weighted [[harmonic mean]] of precision and recall, the traditional F-measure or balanced F-score is:

:<math>F = 2 \cdot (\mathrm{precision} \cdot \mathrm{recall}) / (\mathrm{precision} + \mathrm{recall}).\,</math>

This is also known as the <math>F_1</math> measure, because recall and precision are evenly weighted.

The general formula for non-negative real ß is:
:<math>F_\beta = (1 + \beta^2) \cdot (\mathrm{precision} \cdot \mathrm{recall}) / (\beta^2 \cdot \mathrm{precision} + \mathrm{recall}).\,</math>

Two other commonly used F measures are the <math>F_{2}</math> measure, which weights recall twice as much as precision, and the <math>F_{0.5}</math> measure, which weights precision twice as much as recall.

The F-measure was derived by van Rijsbergen (1979) so that <math>F_\beta</math> "measures the effectiveness of retrieval with respect to a user who attaches ß times as much importance to recall as precision".  It is based on van Rijsbergen's effectiveness measure <math>E = 1-(1/(\alpha/P + (1-\alpha)/R))</math>.  Their relationship is <math>F_\beta = 1 - E</math> where <math>\alpha=1/(\beta^2+1)</math>.

=== Average precision of precision and recall===

The precision and recall are based on the whole list of documents returned by the system. Average precision emphasizes returning more relevant documents earlier. It is average of precisions computed after truncating the list after each of the relevant documents in turn:

:<math> \operatorname{AveP} = \frac{\sum_{r=1}^N (P(r) \times \mathrm{rel}(r))}{\mbox{number of relevant documents}} \!</math> <!-- It /should/ be P@r instead of P(r), but couldn't find the right way to do that -->

where ''r'' is the rank, ''N'' the number retrieved, ''rel()'' a binary function on the relevance of a given rank, and ''P()'' precision at a given cut-off rank.

== Model types ==
[[Image:Information-Retrieval-Models.png|thumb|500px|categorization of IR-models (translated from [http://de.wikipedia.org/wiki/Informationsrückgewinnung#Klassifikation_von_Modellen_zur_Repr.C3.A4sentation_nat.C3.BCrlichsprachlicher_Dokumente German entry], original source [http://www.logos-verlag.de/cgi-bin/engbuchmid?isbn=0514&lng=eng&id= Dominik Kuropka])]]
For the information retrieval to be efficient, the documents are typically transformed into a suitable representation. There are several representations. The picture on the right illustrates the relationship of some common models. In the picture, the models are categorized according to two dimensions: the mathematical basis and the properties of the model.

=== First dimension: mathematical basis ===
* ''Set-theoretic models'' represent documents as sets of words or phrases. Similarities are usually derived from set-theoretic operations on those sets. Common models are:
** [[Standard Boolean model]]
** [[Extended Boolean model]]
** [[Fuzzy retrieval]]

* ''Algebraic models'' represent documents and queries usually as vectors, matrices or tuples. The similarity of the query vector and document vector is represented as a scalar value.
** [[Vector space model]]
** [[Generalized vector space model]]
** Topic-based vector space model (literature: [http://www.kuropka.net/files/TVSM.pdf], [http://www.logos-verlag.de/cgi-bin/engbuchmid?isbn=0514&lng=eng&id=]) 
** [[Extended Boolean model]]
** Enhanced topic-based vector space model (literature: [http://kuropka.net/files/HPI_Evaluation_of_eTVSM.pdf], [http://www.logos-verlag.de/cgi-bin/engbuchmid?isbn=0514&lng=eng&id=])
** Latent semantic indexing aka [[latent semantic analysis]]

* ''Probabilistic models'' treat the process of document retrieval as a probabilistic inference. Similarities are computed as probabilities that a document is relevant for a given query. Probabilistic theorems like the [[Bayes' theorem]] are often used in these models.
** [[Binary independence retrieval]]
** [[Probabilistic relevance model (BM25)]]
** Uncertain inference
** [[Language model]]s
** [[Divergence-from-randomness model]]
** [[Latent Dirichlet allocation]]

=== Second dimension: properties of the model ===
* ''Models without term-interdependencies'' treat different terms/words as independent. This fact is usually represented in vector space models by the [[orthogonality]] assumption of term vectors or in probabilistic models by an [[independency]] assumption for term variables.

* ''Models with immanent term interdependencies'' allow a representation of interdependencies between terms. However the degree of the interdependency between two terms is defined by the model itself. It is usually directly or indirectly derived (e.g. by [[dimension reduction|dimensional reduction]]) from the [[co-occurrence]] of those terms in the whole set of documents.

* ''Models with transcendent term interdependencies'' allow a representation of interdependencies between terms, but they do not allege how the interdependency between two terms is defined. They relay an external source for the degree of interdependency between two terms. (For example a human or sophisticated algorithms.)

<!--
== Research Groups (in no particular order) ==
* [http://ciir.cs.umass.edu/ Center for Intelligent Information Retrieval at University of Massachusetts]
* [http://www.lti.cs.cmu.edu/Research/projects.html#ir Information Retrieval at the Language Technologies Institute, Carnegie Mellon University]
* [http://ir.dcs.gla.ac.uk Glasgow Information Retrieval Group]
-->

== Major figures ==

* [[Gerard Salton]]
* [[Hans Peter Luhn]]
* [http://ciir.cs.umass.edu/personnel/croft.html W. Bruce Croft]
* [[Karen Spärck Jones]]
* [[C. J. van Rijsbergen]]
* [http://www.soi.city.ac.uk/~ser/homepage.html Stephen E. Robertson]

== Awards in the field ==

* [[Tony Kent Strix award]]
* [[Gerard Salton Award]]

== See also ==
* [[Adversarial information retrieval]]
* [[Information retrieval applications|Areas of IR application]]
* [[Clustering]]
* [[Controlled vocabulary]]
* [[Cross Language Evaluation Forum]]
* [[Educational psychology]]
* [[Free text search]]
* [[Human Computer Information Retrieval]]
* [[Information extraction]]
* [[Information need]]
* [[Information Retrieval Facility]]
* [[Information science]]
* [[Knowledge visualization]]
* [[Multisearch]]
* [[Relevance (Information Retrieval)]]
* [[Relevance feedback]]
* [[Index (search engine)|Search index]]
* [[SP theory]]
* [[tf-idf]]

== References ==

<references />

== External links ==
* [http://www.acm.org/sigir/ ACM SIGIR: Information Retrieval Special Interest Group]
* [http://irsg.bcs.org/ BCS IRSG: British Computer Society - Information Retrieval Specialist Group] 
* [http://trec.nist.gov Text Retrieval Conference (TREC)]
* [http://www.cwirf.org/ Chinese Web Information Retrieval Forum (CWIRF)]
* [http://www.dcs.gla.ac.uk/Keith/Preface.html Information Retrieval] (online book) by [[C. J. van Rijsbergen]]
* [http://ir.dcs.gla.ac.uk/wiki/ Information Retrieval Wiki]
* [http://ir-facility.org/ Information Retrieval Facility]
* [http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html Introduction to Information Retrieval (online book) by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Cambridge University Press. 2008.  ]



[[Category:Information retrieval|*]]

[[de:Information-Retrieval]]
[[es:Recuperación de información]]
[[eu:Informazioa eskuratzea]]
[[fa:ذخیره‌سازی و بازیابی اطلاعات]]
[[fr:Recherche d'information]]
[[gl:Recuperación de información]]
[[ko:정보 검색]]
[[it:Information retrieval]]
[[nl:Information retrieval]]
[[ja:情報検索]]
[[no:Informasjonsgjenfinning]]
[[pt:Recuperação de informação]]
[[ru:Информационный поиск]]
[[fi:Tiedonhaku]]
[[tg:Ҷустуҷӯи информатсионӣ]]
[[uk:Інформаційний пошук]]
[[zh:資訊檢索]]