1.0 Background Information

IR: Finding materials that satisfy an information need from unstructured data

Information retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers).

Unstructured data

• No clear structure => difficult for computer Clustering
• Task of producing a suitable grouping of documents based on their contents Classifying
• Task of deciding which class(es) a document within a collection belongs to Scales of IR
• Web Search
  • Billions of documents stored over millions of computers
• Enterprise
  • Internal documents within a corporation's collection, more domain-specific
• Personal Information Retrieval
  • Documents on a personal computer, handled in a lightweight manner

1.1 Boolean Retrieval Problem Simplified

Scenario #1

Consider a collection of plays (Shakespeare's Collected Works)

• Target: Determine which plays contain the words "Brutus" AND "Caesar" AND NOT "Calpurnia".
• Simple Method: Linear scan through collection (or grepping), positive result if target conditions of query are satisfied
  • Note for each play whether it has "Brutus" and "Caesar", exclude if it contains "Calpurnia"
• Limits of simple method
  • Can't process large collections efficiently
  • Inflexible matching operations (e.g. if we want a query with definable relationships between words instead of just logical)
  • Doesn't pick the best answer (not ranked retrieval)
• Overcoming linear scans: Consider indexing the documents in advance
  • Method
    • For each document, record whether it contains each word out of all the words Shakespeare has used (approximately 32,000 words)
    • Results in binary term-document incidence matrix (Fig. 1.1). The terms are indexed units.

      • "term-document" as in a term-to-document relationship within the matrix. "binary" as in values are only true or false

    • Refer to Fig. 1.1
    • We can have either a column vector (for each document, show the occurring terms), OR a row vector (for each term, show the documents it occurs in)
    • To solve initial proposed target, we take row vectors for Brutus, Caesar, and Calpurnia, and perform a bitwise AND operation
    • Result: 110100 AND 110111 AND 101111 = 100100. Hence, Antony and Cleopatra and Hamlet are the answers.

      • Note that we invert the last column vector (Calpurnia) in order to satisfy the NOT operator in our query

The Boolean retrieval model allows us to pose a query in the form of a Boolean expression of terms. Each document is viewed as a set of words.

Scenario #2

Consider a larger-scale scenario with a collection of N = 1 million documents that are roughly 1000 words long each. Generally, there might be about M = 500,000 distinct terms throughout the collection.

• Goal: Address the ad hoc retrieval task where we aim to provide documents relevant (perceived as containing information of value with respect to their need) to some user information need (topic which user wants to know more about), communicated through a one-off, user query (what user conveys to computer to try to communicate their need)
• Assessing effectiveness (quality of search results)
  • Precision
    • Fraction of returned results that are relevant to the information need
  • Recall
    • Fraction of relevant documents in the collection that were actually returned
• Limit: term-document matrix is not a viable solution, too large.
  • However, note that there are few non-zero entries because each document is only a 1000 words long.

    • Matrix would have 500,000 rows (distinct terms) * 1,000,000 columns (documents) = 500 billion cells. Since each document has a general length of being a 1000 words long, assuming all terms in each document are distinct, at most 1,000,000 documents * 1000 distinct terms per document = 1 billion. So there is a maximum of 1 billion 1's out of 500 billions cells. 99.8% of the cells are zero.

• Overcome limit: Record only the 1 positions.
  • Inverted index
    • Concept
      • Keep a dictionary (refers to the data structure used) of terms.
      • For each term, there will be a list that records which documents the term occurs in
      • , Each item in the list is called a posting
      • The list is known as a postings list
      • All postings lists are collectively known as the postings

1.2 Building an inverted index

Steps

1. Collect documents to be indexed
2. Tokenize text so each document is a list of tokens
3. Preprocessing to normalise tokens
4. Index documents that each term occurs in by creating an inverted index

Consider a scenario in which steps 1-3 are done. Now we perform step 4. Indexing Method

• Assign each document a unique docID
• Input to indexing method will be pairs of term and docID (Fig. 1.4)
• Sort the list with terms alphabetically
• Merge terms that repeat in the same document
• Group instances of the same term
• Split them into dictionary and postings
• Sort postings by docID

Singly linked lists or variable length arrays are good structures for postings lists.

1.3 Processing Boolean queries

Target: Combine inverted index and Boolean retrieval model Consider the statement: Brutus AND Calpurnia

• Locate Brutus in Dictionary
• Get its postings
• Locate Calpurnia in Dictionary
• Get its postings
• Intersect the postings lists
  • Simple intersection algorithm

    • INTERSECT(p1, p2)
          answer <- {}
          while p1 != NIL and p2 != NIL
          do if docID(p1) = docID(p2)
        	  then ADD(answer, docID(p1))
        		  p1 <- next(p1)
        		  p2 <- next(p2)
        	  else if docID(p1) < docID(p2)
        		  then p1 <- next(p1)
        		  else p2 <- next(p2)
          return answer
      // x+y intersections are done where x = size(doc(p1)), y = size(doc(p2))

Through this form of indexing, complexity is improved by a constant (although still linear), but it's a huge difference in practice.

Query optimisation is the process of selecting how to organise the work of answering a query so that the system does minimal work.

Consider a query that is an AND of t terms, optimise intersection by:

• Intersecting the two smallest postings lists
• All intermediate results will be at most the size of the smallest postings list

  • "intermediate" in the sense that they are temporary results that come after the starting result, working towards the final result

  • Code:

    • INTERSECT({t1, ..., tn})
          terms <- SORTBYINCREASINGFREQUENCY({t1, ..., tn})
          result <- postings(first(terms))
          terms <- rest(terms)  // rest of the terms
          while terms != NIL and result != NIL
          do result <- INTERSECT(result, postings(first(terms)))
        	  terms <- rest(terms)
          return result

  • If you have a hard time accepting it, try going through this scenario. Let N1=2, N2=100, N3=50 where Nn represents the size of the postings list. Now see what happens when you compare N2 and N3 first instead of N1 and N3.

Many ways to modify and optimise intersection depending on the situation. Even the standard intersection algorithm is essential in certain cases.

1.4 Extended B.R.M. vs Ranked Retrieval

Some systems have extended the Boolean retrieval model by incorporating operators such as term proximity operators (helps specify that two terms must occur within a certain distance of each other).

Problems with B.R.M.

• Document either matches query or does not
• AND operators lead to high precision but low recall
• OR gives low precision but high recall
• Lack of middle ground

Ranked retrieval models (like vector space models) possess certain advantages, and allows for free text queries.

Figures

• Brutus -> {1, 2, 4, 11, 31, 45, 173, 174}
• Caesar -> {1, 2, 4, 5, 6, 16, 57, 132, ...}
• Calpurnia -> {2, 31, 54, 101}
• LHS: Dictionary
• RHS: Postings

Fig. 1.4