A History of Information Retrieval

The methods taught in an information retrieval course were not designed together. Each one answered a specific problem at a specific time, under the constraints of the hardware and the data then available. Inverse document frequency came from a study of why some index terms were more useful than others. BM25 was refined over several years of a shared evaluation. PageRank answered the problem that text matching alone could not separate good web pages from bad ones. Knowing which problem a method was built for explains both why it works and where it fails.

This article follows the field through its main problems. It draws on the histories by Sanderson and Croft (2012) and Harman (2019), which give fuller accounts.

Before computers: too much to read

The problem predates digital computers. Scientific publication grew rapidly in the first half of the twentieth century, and by the end of the Second World War it was clear that researchers could no longer keep up with the literature in their own fields.

In 1945, Vannevar Bush, who had directed U.S. wartime research, published "As We May Think" in The Atlantic Monthly. He described the memex, a hypothetical desk "in which an individual stores all his books, records, and communications, and which is mechanized so that it may be consulted with exceeding speed and flexibility." Bush's central criticism was of indexing itself. Libraries filed information alphabetically or by subject, in a single place, and retrieved it by following a classification down a hierarchy. "The human mind does not work that way," he wrote. "It operates by association." The memex would let a reader link any item to any other and save the resulting trails. It was never built, and it anticipated hypertext more than search engines, but it framed the goal: machine support for finding information in a body of material too large to remember.

Machines for searching documents already existed. Emanuel Goldberg patented a "statistical machine" in 1931 that searched microfilmed records for a coded pattern using a photoelectric cell (Buckland, 1992). Bush himself had built a microfilm "rapid selector" at MIT before the war. Calvin Mooers developed Zatocoding, a system of edge-notched cards on which several descriptors were superimposed in a single coded field, and around 1950 he gave the field its name: information retrieval. These systems were mechanical, but they established that retrieval meant matching a request against a representation of each document, not reading the documents themselves.

Counting words

The first ideas that still appear in modern systems came from Hans Peter Luhn at IBM in the late 1950s. Luhn (1957) proposed that the frequency of a word in a document indicates how important the word is to it, and that a request could be matched against documents by the overlap of their words, with no human indexer in between. In 1958 he applied the same statistics to produce abstracts automatically. That paper included an observation that later reappeared as stop-word removal and term weighting: the most frequent words in a text, such as articles and prepositions, carry little meaning, the rarest words are too rare to be reliable, and the significant words lie in between. Term statistics sets this band against the word-frequency distribution of a real collection.

Luhn also proposed selective dissemination of information (1958): each reader's interests would be stored as a profile, and new documents would be matched against all profiles as they arrived. This is information filtering, the standing-query counterpart of search that underlies alerting services and news feeds today.

A different line of thought appeared at the same time. Maron and Kuhns (1960) argued that a system cannot know with certainty whether a document is relevant, so it should estimate the probability of relevance and rank documents by that estimate. The idea would take another fifteen years to develop into working models.

Does any of this work?

By the late 1950s many indexing methods had been proposed: controlled vocabularies, faceted classification, keyword systems, and statistical methods. There was no reliable way to tell which was best. Librarians and documentalists argued from experience and principle.

Cyril Cleverdon, librarian at the College of Aeronautics in Cranfield, England, set out to settle the question experimentally. The Cranfield experiments, run in two rounds from the late 1950s to the mid-1960s, created a collection of documents, a set of questions, and for each question a judgment of which documents were relevant to it. Different indexing languages could then be compared by how well they retrieved the documents judged relevant, measured by recall (the fraction of relevant documents retrieved) and precision (the fraction of retrieved documents that were relevant).

The results surprised the field. In the second round of experiments, on a collection of 1,400 papers in aeronautics, simple indexing using single words taken from the documents performed as well as or better than elaborate controlled vocabularies built by experts (Cleverdon, 1967). The finding was resisted for years, but it justified automatic indexing, and the method outlasted the result. A test collection of documents, queries, and relevance judgments, together with a measure computed from them, remains the basic instrument of the field. The evaluation topic describes it in detail.

Boolean systems in practice

The first large operational systems used Boolean retrieval: a query combines terms with AND, OR, and NOT, and the system returns exactly the documents that satisfy the expression. The U.S. National Library of Medicine's MEDLARS began batch searching of the medical literature in 1964 and went online as MEDLINE in 1971. Lockheed's Dialog service opened commercially in 1972, LEXIS began full-text legal search in 1973, and Westlaw followed in 1975.

Boolean retrieval suited these settings. Searches were run by trained intermediaries, typically librarians, who could build long and precise queries. Results were predictable and could be explained, and the computers of the time could evaluate set operations on sorted lists efficiently. The model's weaknesses were also clear. It offers no ranking, so a query either returns too many documents to read or too few to be useful, and the searcher adjusts the query by trial and error. A document that satisfies four of five ANDed terms is excluded entirely.

Professional searchers kept Boolean retrieval for decades after ranked alternatives appeared, for reasons described in search in professional domains. The Boolean retrieval topic covers the model and its query processing.

Ranking

While commercial systems used Boolean retrieval, researchers developed models that score every document and rank the results.

The longest-running effort was Gerard Salton's SMART system, begun at Harvard in the early 1960s and continued at Cornell from 1965. SMART was an experimental platform, not a product, and over three decades it was used to test term weighting, document length normalization, relevance feedback, and clustering on the test collections of the day. From it came the vector space model: documents and queries are represented as vectors of term weights, and documents are ranked by the similarity of their vectors to the query vector, typically the cosine of the angle between them (Salton, Wong, and Yang, 1975). Partial matching followed naturally, since a document missing one query term could still rank highly. J. J. Rocchio's relevance feedback method (1971), developed within SMART, moved the query vector toward documents the user marked relevant and away from those marked nonrelevant.

The weights mattered as much as the model. Karen Spärck Jones (1972) observed that a term occurring in many documents is a poor discriminator, and proposed weighting terms by a decreasing function of the number of documents containing them. Combined with Luhn's within-document frequency, this inverse document frequency became TF-IDF weighting, which remains the most widely known term weighting scheme in the field.

The probabilistic line matured in the same decade. Stephen Robertson and Karen Spärck Jones (1976) derived term weights from the probability that a term appears in relevant and nonrelevant documents, the model now called the Binary Independence Model. Robertson (1977) stated the Probability Ranking Principle, which shows that ranking by probability of relevance is optimal under stated assumptions. C. J. van Rijsbergen's textbook (1979) collected these results. By 1980 the main families of ranking models existed, but they had been tested only on collections of a few thousand documents, and practitioners doubted that results from such small collections would carry over to operational systems with millions of documents.

Scale and a common benchmark

The doubt began to be answered in 1992, when the U.S. National Institute of Standards and Technology (NIST), with DARPA, started the Text REtrieval Conference (TREC) under Donna Harman. TREC distributed a collection of about two gigabytes of newswire and government documents, far larger than any previous test collection, with new topics each year. Participating groups ran their systems on the same topics and submitted rankings. NIST then assembled relevance judgments by pooling the top-ranked documents from all submissions.

TREC changed how research was done. Systems could be compared directly, ideas that worked spread quickly between groups, and results were obtained at a realistic scale. Voorhees and Harman (2005) report that the effectiveness of participating systems roughly doubled over TREC's first several years. One of the most durable results came from City University London, where Robertson, Walker, and colleagues refined their Okapi system over successive TRECs. The ranking function they reported at TREC-3, BM25, added term frequency saturation and document length normalization to the probabilistic weights of the 1970s (Robertson et al., 1995). It remains a standard baseline, and in 2016 it became the default similarity in Apache Lucene, the library underneath Elasticsearch and Solr.

TREC also widened the field through tracks for specific tasks: filtering, cross-language retrieval, spoken documents, question answering, web search, and later medical, legal, and conversational search. Many tracks created test collections that are still in use, and several founded research areas of their own.

The web

The web raised retrieval to a new scale and introduced a problem the field had not faced: documents written to be found. Early web search engines such as Lycos, Excite, and AltaVista (1994–1995) indexed tens of millions of pages and ranked them mostly by text matching. Two difficulties quickly appeared. Short queries matched huge numbers of pages, and text-matching scores could not separate an authoritative page from an obscure or deceptive one. Page authors also learned that repeating popular terms raised their rankings, which made spam a permanent part of web retrieval.

The answer was to use the structure of the web itself. A hyperlink can be read as a judgment by one author that another page is worth visiting. Jon Kleinberg's HITS algorithm (1999) gave each page in the neighborhood of a query's results two scores: a good authority is linked to by good hubs, and a good hub links to good authorities, each score defined recursively through the other. Sergey Brin and Lawrence Page's PageRank (Brin and Page, 1998) instead assigned every page a single, query-independent score, the long-run probability that a random surfer following links visits it, so that links from high-ranking pages count for more. Google combined PageRank with text matching and with anchor text, the words of links pointing to a page, which often describe it better than the page describes itself. The web crawling topic covers how such collections are gathered and the PageRank article covers link analysis.

The web also brought query logs. A search engine serving millions of people records which queries they issue, which results they click, and when they reformulate. These logs provided a new source of evidence about relevance, and at a scale no assessor pool could match.

Statistical language models for retrieval appeared in the same period (Ponte and Croft, 1998). Instead of estimating the probability of relevance, they rank documents by the probability that a language model estimated from the document would generate the query. This gave the field a third principled family of models alongside vector space and probabilistic relevance.

Learning to rank

By the 2000s, web search engines used hundreds of signals: several text-matching scores for different fields, link-based authority, freshness, URL structure, click statistics, and spam indicators. Combining them by hand-tuned formulas did not scale. Learning to rank treats the combination as a supervised machine learning problem: given queries, documents represented as feature vectors, and relevance labels, learn a function that orders documents well. Early work dates to Fuhr (1989), but the approach became standard in industry in the mid-2000s with methods such as RankNet (Burges et al., 2005) and the gradient-boosted tree rankers that followed it. Liu (2009) surveys the methods. The classical models did not disappear; their scores became features in the learned ranker.

Neural retrieval

The most recent shift replaces hand-designed representations with learned ones. Word embeddings, which came into wide use after word2vec (Mikolov et al., 2013) made them cheap to train on large corpora, represented words as vectors in which related words lie close together, offering a partial answer to vocabulary mismatch. In 2019, Nogueira and Cho showed that the pretrained language model BERT, fine-tuned to judge whether a passage answers a query, substantially outperformed previous methods at re-ranking candidates retrieved by BM25. Dense retrieval followed: queries and documents are each encoded as a single vector, and retrieval becomes a nearest-neighbor search in that vector space (Karpukhin et al., 2020). Unlike the re-ranker, which reads the query and passage together, this design encodes documents independently of any query, so their vectors can be computed and indexed in advance. Retrieval-augmented generation connects retrieval to large language models, which answer a question by reading passages a retriever has supplied (Lewis et al., 2020).

These methods have not made the classical ones obsolete. On the BEIR benchmark, which tests systems on collections different from those they were trained on, BM25 remained competitive with, and on several collections better than, the dense retrievers of the time (Thakur et al., 2021). Production systems commonly use a fast lexical method to retrieve candidates and a neural model to re-rank them.

Problems, answers, and where they are taught

The history can be read backwards as a guide to the course. Each row below pairs a problem with the idea that answered it and the article where that idea is worked through in detail.

The course retraces much of this sequence, with one large exception: evaluation, which came early in history, is taught after the first ranking models, once there are rankings to compare. Reading each method as the answer to a problem its predecessor could not solve is often the quickest way into it.

Patterns in the history

Three patterns run through this history and recur throughout the course.

Ideas accumulate. New methods rarely replace old ones. They absorb them. Boolean operators survive in advanced-search interfaces and in the filters of every product search. Luhn's term frequency and Spärck Jones's inverse document frequency survive in BM25, which survives as the first stage of neural pipelines and as a feature in learned rankers. Salton's vectors reappear, learned instead of counted, as dense embeddings. Studying the older methods explains the parts of current systems.

Progress follows evaluation. Ranked retrieval models existed for twenty years before TREC showed at scale that they worked, and learned rankers became practical when query logs supplied training data. The major advances in the field came when a new idea, a way to test it, and the computing resources to apply it became available at the same time.

Formal structure meets uncertain language. Each model imposes some structure on text, whether logic, geometry, probability, or a learned vector space, and each eventually encounters the ambiguity of natural language that the structure does not capture. Rule-based linguistic methods lost to statistical ones, statistical methods could not handle synonymy, and neural methods match meaning more flexibly but are harder to explain and can reproduce the biases of their training data. No approach has made the relevance problem disappear, and each new one has had to be judged by the same experimental method that Cleverdon introduced in the 1960s.

References

• Brin, S., and Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.
• Buckland, M. K. (1992). Emanuel Goldberg, electronic document retrieval, and Vannevar Bush's Memex. Journal of the American Society for Information Science, 43(4), 284–294.
• Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and Hullender, G. (2005). Learning to rank using gradient descent. In Proceedings of ICML 2005, 89–96.
• Bush, V. (1945). As we may think. The Atlantic Monthly, 176(1), 101–108.
• Cleverdon, C. W. (1967). The Cranfield tests on index language devices. Aslib Proceedings, 19(6), 173–194.
• Fuhr, N. (1989). Optimum polynomial retrieval functions based on the probability ranking principle. ACM Transactions on Information Systems, 7(3), 183–204.
• Harman, D. (2019). Information retrieval: The early years. Foundations and Trends in Information Retrieval, 13(5), 425–577.
• Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W. (2020). Dense passage retrieval for open-domain question answering. In Proceedings of EMNLP 2020, 6769–6781.
• Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5), 604–632.
• Lewis, P., Perez, E., Piktus, A., et al. (2020). Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems 33.
• Liu, T.-Y. (2009). Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 3(3), 225–331.
• Luhn, H. P. (1957). A statistical approach to mechanized encoding and searching of literary information. IBM Journal of Research and Development, 1(4), 309–317.
• Luhn, H. P. (1958). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159–165.
• Luhn, H. P. (1958). A business intelligence system. IBM Journal of Research and Development, 2(4), 314–319.
• Maron, M. E., and Kuhns, J. L. (1960). On relevance, probabilistic indexing and information retrieval. Journal of the ACM, 7(3), 216–244.
• Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013). Efficient estimation of word representations in vector space. arXiv:1301.3781.
• Nogueira, R., and Cho, K. (2019). Passage re-ranking with BERT. arXiv:1901.04085.
• Ponte, J. M., and Croft, W. B. (1998). A language modeling approach to information retrieval. In Proceedings of SIGIR 1998, 275–281.
• Robertson, S. E. (1977). The probability ranking principle in IR. Journal of Documentation, 33(4), 294–304.
• Robertson, S. E., and Spärck Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3), 129–146.
• Robertson, S. E., Walker, S., Jones, S., Hancock-Beaulieu, M. M., and Gatford, M. (1995). Okapi at TREC-3. In Overview of the Third Text REtrieval Conference (TREC-3), NIST Special Publication 500-225, 109–126.
• Rocchio, J. J. (1971). Relevance feedback in information retrieval. In G. Salton (Ed.), The SMART Retrieval System: Experiments in Automatic Document Processing, 313–323. Prentice-Hall.
• Salton, G., Wong, A., and Yang, C. S. (1975). A vector space model for automatic indexing. Communications of the ACM, 18(11), 613–620.
• Sanderson, M., and Croft, W. B. (2012). The history of information retrieval research. Proceedings of the IEEE, 100 (Special Centennial Issue), 1444–1451.
• Spärck Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1), 11–21.
• Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., and Gurevych, I. (2021). BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Proceedings of the NeurIPS 2021 Datasets and Benchmarks Track.
• van Rijsbergen, C. J. (1979). Information Retrieval, 2nd edition. Butterworths.
• Voorhees, E. M., and Harman, D. K. (Eds.) (2005). TREC: Experiment and Evaluation in Information Retrieval. MIT Press.