Information Retrieval - Basic Techniques

Subscribe Send me a message home page


Note: this is a reading note of the book Information Retrieval: Implementing and Evaluating Search Engines.

In this post, we will briefly talk about some basic techniques used in information retrieval systems. We first describe the inverted index, a core data structure used in most IR system. Then we present three common techniques to retrieve information from a collection of documents. Finally, we describe methods that can be used to evaluate the performance of IR system.

1. Inverted Index

An inverted index is a mapping between terms and their locations of occurrence in a text collection \(C\). It's the central data structure used in information retrieval system.

We further assume the following methods are available:

inverted_index.png

Summary Of Notation

summary_of_notation.jpg

Example: Phrase Search

Definition. A phrase is a list of terms enclosed in double quotes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def nextPhrase(listOfTerms, currentPos):
    """
    Find the next occurrence of the phrase after the current position.

    @listOfTerms: terms in the phrase.
    @currentPos: current position in the text.

    @return: [startPos, endPos] where statPos is the start location of the next phrase and endPos is
             the end location of the next phrase.
    """
    v = currentPos

    for term in listOfTerms:
        v = next(term, v)

    if v == END_OF_COLLECTION:
        return [END_OF_COLLECTION, END_OF_COLLECTION]

    u = v
    n = len(listOfTerms)
    for i in range(1, n + 1):
        k = n - i
        u = prev(listOfTerms[k])

    if v - u == n - 1:
        return [u, v]
    else:
        return nextPhrase(listOfTerms, u)

As we can see here the algorithm is straightforward if the inverted index and those four methods mentioned earlier are available.

2. Document-Oriented Index

Sometimes it is helpful to treat document as the unit of retrieval. Here the document is a general concept. It can be a text file, a chapter in the book or just a couple lines in a paragraph. A document-oriented index is a schema-dependent index and the location of a term is characterized by two numbers: (1) document id and (2) the offset in that document.

We can think of document-oriented index as a kind of "batch processing" and some of the statistics about term and document can provide valuable information, such as

3. Retrieval and Ranking

There are three common approaches

The first approach TF-IDF uses vectors in a high dimensional space to represent documents and queries. The result of the query is a list of ranked documents. The document that is most similar to the query has the highest ranking. This is one of the classic retrieval methods. However, it's overtaken by modern probability and machine learning based approaches.

The second approach is Proximity Ranking. The idea is simple: if the terms in the query are close together in a document, then that document may be relevant to the query. Similar to the phrase search algorithm, we will find covers in documents. A cover is a range [u, v] such that (1) [u, v] is inside a document and (2) [u, v] contains all terms in the query.

The third approach is called Boolean Filter. Strictly speaking, this is not a ranking method. As the name indicates, it's a filter. Boolean operators AND, OR and NOT are used in the query. The implementation is, once again, similar to the phrase search algorithm. This time, we need to find the documentation range [doc_u, doc_v] such that the documents within this range jointly satisfy the query. If the range is of size 1 then the range is reduced to one single document, which satisfies the query.

4. Evaluation

Recall and precision are two widely used effectiveness measures. A trade-off frequently exists between them, such that increasing recall leads to a corresponding decrease in precision. The efficiency is usually measured by response time.

recall_and_precision.png

----- END -----

Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png


Comments