Home | Sources Directory | News Releases | Calendar | Articles | RSS Sources Select News RSS Feed | Contact |  

Information retrieval

Information retrieval (IR) is the science of searching for documents, for information within documents, and for metadata about documents, as well as that of searching relational databases 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, and technologies. IR is interdisciplinary, based on computer science, mathematics, library science, information science, information architecture, cognitive psychology, linguistics, and statistics.

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


[edit] History

â 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's Dracula, 1897

The idea of using computers to search for relevant pieces of information was popularized in the article As We May Think by Vannevar Bush in 1945.[1] The first automated information retrieval systems were introduced in the 1950s and 1960s. By 1970 several different techniques had been shown to perform well on small text corpora such as the Cranfield collection (several thousand documents).[1] Large-scale retrieval systems, such as the Lockheed Dialog system, came into use early in the 1970s.

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 scale to huge corpora. The introduction of web search engines 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.

[edit] Timeline

  • Before the 1900s
    1880s: Herman Hollerith invents the recording of data on a machine readable medium.
    1890 Hollerith cards, key punches and tabulators used to process the 1890 US Census data.
  • 1940sâ1950s
    late 1940s: The US military confronted problems of indexing and retrieval of wartime scientific research documents captured from Germans.
    1945: Vannevar Bush's As We May Think appeared in Atlantic Monthly.
    1947: Hans Peter Luhn (research engineer at IBM since 1941) began work on a mechanized punch card-based system for searching chemical compounds.
    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).
    1950: The term "information retrieval" appears to have been coined by Calvin Mooers.
    1951: Philip Bagley conducted the earliest experiment in computerized document retrieval in a master thesis at MIT.[2]
    1955: Allen Kent joined Case Western Reserve University, and eventually became associate director of the Center for Documentation and Communications Research. That same year, Kent and colleagues published a paper in American Documentation describing the precision and recall measures as well as detailing a proposed "framework" for evaluating an IR system which included 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."
  • 1960s:
    early 1960s: Gerard Salton began work on IR at Harvard, later moved to Cornell.
    1960: Melvin Earl (Bill) Maron and John Lary Kuhns[3] published "On relevance, probabilistic indexing, and information retrieval" in the Journal of the ACM 7(3):216â244, July 1960.
    • 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 Collection of Aeronautics, Cranfield, England, 1962.
    • Kent published Information Analysis and Retrieval.
    • 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.
    • 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).
    • Karen Spärck Jones finished her thesis at Cambridge, Synonymy and Semantic Classification, and continued work on computational linguistics as it applies to IR.
    • 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.
    • National Library of Medicine developed MEDLARS Medical Literature Analysis and Retrieval System, the first major machine-readable database and batch-retrieval system.
    • 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.
    late 1960s: F. Wilfrid Lancaster completed evaluation studies of the MEDLARS system and published the first edition of his text on information retrieval.
    • Gerard Salton published Automatic Information Organization and Retrieval.
    • John W. Sammon, Jr.'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.
  • 1970s
    early 1970s:
    • First online systemsâNLM's AIM-TWX, MEDLINE; Lockheed's Dialog; SDC's ORBIT.
    • Theodor Nelson promoting concept of hypertext, published Computer Lib/Dream Machines.
    1971: Nicholas Jardine and Cornelis 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, December 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 ACM SIGIR conference.
    1979: C. J. van Rijsbergen published Information Retrieval (Butterworths). Heavy emphasis on probabilistic models.
  • 1980s
    1980: First international ACM SIGIR conference, joint with British Computer Society IR group in Cambridge.
    1982: Nicholas J. Belkin, Robert N. Oddy, and Helen M. 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 Michael J. 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 Donald B. Crouch, Robert R. Korfhage, Matthew Chalmers, Anselm Spoerri and others.
    1989: First World Wide Web proposals by Tim Berners-Lee at CERN.
  • 1990s
    1992: First TREC conference.
    1997: Publication of Korfhage's Information Storage and Retrieval[4] with emphasis on visualization and multi-reference point systems.
    late 1990s: Web search engines implementation of many features formerly found only in experimental IR systems. Search engines become the most common and maybe best instantiation of IR models, research, and implementation.

[edit] Overview

An information retrieval process begins when a user enters a query into the system. Queries are formal statements of information needs, 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 relevancy.

An object is an entity that is represented by information in a database. User queries are matched against the database information. Depending on the application the data objects may be, for example, text documents, images[5], audio[6], mind maps[7] 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 or metadata.

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.[8]

[edit] Performance measures

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.

[edit] Precision

Precision is the fraction of the documents retrieved that are relevant to the user's information need.

 \mbox{precision}=\frac{|\{\mbox{relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{retrieved documents}\}|}

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.

[edit] Recall

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

\mbox{recall}=\frac{|\{\mbox{relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{relevant documents}\}|}

In binary classification, recall is called 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.

[edit] Fall-Out

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

 \mbox{fall-out}=\frac{|\{\mbox{non-relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{non-relevant documents}\}|}

In binary classification, fall-out is closely related to specificity (1 â specificity). 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.

[edit] F-measure

The weighted harmonic mean of precision and recall, the traditional F-measure or balanced F-score is:

F = \frac{2 \cdot \mathrm{precision} \cdot \mathrm{recall}}{(\mathrm{precision} + \mathrm{recall})}.\,

This is also known as the F1 measure, because recall and precision are evenly weighted.

The general formula for non-negative real î is:

F_\beta = \frac{(1 + \beta^2) \cdot (\mathrm{precision} \cdot \mathrm{recall})}{(\beta^2 \cdot \mathrm{precision} + \mathrm{recall})}\,.

Two other commonly used F measures are the F2 measure, which weights recall twice as much as precision, and the F0.5 measure, which weights precision twice as much as recall.

The F-measure was derived by van Rijsbergen (1979) so that Fî "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 E = 1 â (1 / (î / P + (1 â î) / R)). Their relationship is Fî = 1 â E where î = 1 / (î2 + 1).

[edit] Mean Average precision

Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. Average precision emphasizes ranking relevant documents higher. It is the average of precisions computed at the point of each of the relevant documents in the ranked sequence:

 \operatorname{AveP} = \frac{\sum_{r=1}^N (P(r) \times \mathrm{rel}(r))}{\mbox{number of relevant documents}} \!

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

 \mbox{P(r)} = \frac{|\{\mbox{relevant retrieved documents of rank r or less}\}|}{r}

This metric is also sometimes referred to geometrically as the area under the Precision-Recall curve.

Note that the denominator (number of relevant documents) is the number of relevant documents in the entire collection, so that the metric reflects performance over all relevant documents, regardless of a retrieval cutoff. See: [9].

[edit] Discounted cumulative gain

DCG uses a graded relevance scale of documents from the result set to evaluate the usefulness, or gain, of a document based on its position in the result list. The premise of DCG is that highly relevant documents appearing lower in a search result list should be penalized as the graded relevance value is reduced logarithmically proportional to the position of the result.

The DCG accumulated at a particular rank position p is defined as:

 \mathrm{DCG_{p}} = rel_{1} + \sum_{i=2}^{p} \frac{rel_{i}}{\log_{2}i}

Since result set may vary in size among different queries or systems, to compare performances the normalised version of DCG uses an ideal DCG - by sorting documents of a result list by relevance - to normalize the score:

 \mathrm{nDCG_{p}} = \frac{DCG_{p}}{IDCG{p}}

The nDCG values for all queries can be averaged to obtain a measure of the average performance of a ranking algorithm. Note that in a perfect ranking algorithm, the DCGp will be the same as the IDCGp producing an nDCG of 1.0. All nDCG calculations are then relative values on the interval 0.0 to 1.0 and so are cross-query comparable.

[edit] Other Measures

[edit] Model types

Categorization of IR-models (translated from German entry, original source 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.

[edit] First dimension: mathematical basis

[edit] 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 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.)

[edit] Major figures

[edit] Awards in the field

[edit] See also

[edit] References

  1. ^ a b Singhal, Amit (2001). "Modern Information Retrieval: A Brief Overview". Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 24 (4): 35â43. http://singhal.info/ieee2001.pdf. 
  2. ^ Doyle, Lauren; Becker, Joseph (1975). Information Retrieval and Processing. Melville. pp. 410 pp.. ISBN 0471221511. 
  3. ^ Maron, Melvin E. (2008). "An Historical Note on the Origins of Probabilistic Indexing". Information Processing and Management 44: 971â972. doi:10.1016/j.ipm.2007.02.012. http://yunus.hacettepe.edu.tr/~tonta/courses/spring2008/bby703/maron-on-probabilistic%20indexing-2008.pdf. 
  4. ^ Korfhage, Robert R. (1997). Information Storage and Retrieval. Wiley. pp. 368 pp.. ISBN 978-0-471-14338-3. http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471143383,descCd-authorInfo.html. 
  5. ^ Goodrum, Abby A. (2000). "Image Information Retrieval: An Overview of Current Research". Informing Science, 3(2) 
  6. ^ Foote, Jonathan (1999). "An overview of audio information retrieval". Multimedia Systems. Springer 
  7. ^ Beel, Jöran; Gipp, Bela; Stiller, Jan-Olaf (2009). "Information Retrieval On Mind Maps - What Could It Be Good For?". Proceedings of the 5th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom'09). Washington: IEEE. http://www.sciplore.org/publications_en.php 
  8. ^ Frakes, William B. (1992). Information Retrieval Data Structures & Algorithms. Prentice-Hall, Inc.. ISBN 0-13-463837-9. http://www.scribd.com/doc/13742235/Information-Retrieval-Data-Structures-Algorithms-William-B-Frakes. 
  9. ^ Turpin, Andrew; Scholer, Falk (2006). "User performance versus precision measures for simple search tasks". Proceedings of the 29th Annual international ACM SIGIR Conference on Research and Development in information Retrieval (Seattle, Washington, USA, August 06-11, 2006) (New York, NY: ACM): 11â18. doi:10.1145/1148170.1148176. 

[edit] External links

Related Articles & Resources

Sources Subject Index - Experts, Sources, Spokespersons

Sources Select Resources Articles

This article is based on one or more articles in Wikipedia, with modifications and additional content by SOURCES editors. This article is covered by a Creative Commons Attribution-Sharealike 3.0 License (CC-BY-SA) and the GNU Free Documentation License (GFDL). The remainder of the content of this website, except where otherwise indicated, is copyright SOURCES and may not be reproduced without written permission. (For information call 416-964-7799 or use the Contact form.)

SOURCES.COM is an online portal and directory for journalists, news media, researchers and anyone seeking experts, spokespersons, and reliable information resources. Use SOURCES.COM to find experts, media contacts, news releases, background information, scientists, officials, speakers, newsmakers, spokespeople, talk show guests, story ideas, research studies, databases, universities, associations and NGOs, businesses, government spokespeople. Indexing and search applications by Ulli Diemer and Chris DeFreitas.

For information about being included in SOURCES as a expert or spokesperson see the FAQ or use the online membership form. Check here for information about becoming an affiliate. For partnerships, content and applications, and domain name opportunities contact us.

Sources home page