Combination schemes

The strategies of biword indexes and positional indexes can be fruitfully combined. If users commonly query on particular phrases, such as Michael Jackson, it is quite inefficient to keep merging positional postings lists. A combination strategy uses a phrase index, or just a biword index , for certain queries and uses a positional index for other phrase queries. Good queries to include in the phrase index are ones known to be common based on recent querying behavior. But this is not the only criterion: the most expensive phrase queries to evaluate are ones where the individual words are common but the desired phrase is comparatively rare. Adding Britney Spears as a phrase index entry may only give a speedup factor to that query of about 3, since most documents that mention either word are valid results, whereas adding The Who as a phrase index entry may speed up that query by a factor of 1000. Hence, having the latter is more desirable, even if it is a relatively less common query.

Williams et al. (2004) evaluate an even more sophisticated scheme which employs indexes of both these sorts and additionally a partial next word index as a halfway house between the first two strategies. For each term, a next word index records terms that follow it in a document. They conclude that such a strategy allows a typical mixture of web phrase queries to be completed in one quarter of the time taken by use of a positional index alone, while taking up 26% more space than use of a positional index alone.

Exercises.

• Assume a biword index. Give an example of a document which will be returned for a query of New York University but is actually a false positive which should not be returned.

• Shown below is a portion of a positional index in the format: term: doc1: $\langle$position1, position2, ...$\rangle$; doc2: $\langle$position1, position2, ...$\rangle$; etc.

  angels: 2: $\langle$36,174,252,651$\rangle$; 4: $\langle$12,22,102,432$\rangle$; 7: $\langle$17$\rangle$;
  fools: 2: $\langle$1,17,74,222$\rangle$; 4: $\langle$8,78,108,458$\rangle$; 7: $\langle$3,13,23,193$\rangle$;
  fear: 2: $\langle$87,704,722,901$\rangle$; 4: $\langle$13,43,113,433$\rangle$; 7: $\langle$18,328,528$\rangle$;
  in: 2: $\langle$3,37,76,444,851$\rangle$; 4: $\langle$10,20,110,470,500$\rangle$; 7: $\langle$5,15,25,195$\rangle$;
  rush: 2: $\langle$2,66,194,321,702$\rangle$; 4: $\langle$9,69,149,429,569$\rangle$; 7: $\langle$4,14,404$\rangle$;
  to: 2: $\langle$47,86,234,999$\rangle$; 4: $\langle$14,24,774,944$\rangle$; 7: $\langle$199,319,599,709$\rangle$;
  tread: 2: $\langle$57,94,333$\rangle$; 4: $\langle$15,35,155$\rangle$; 7: $\langle$20,320$\rangle$;
  where: 2: $\langle$67,124,393,1001$\rangle$; 4: $\langle$11,41,101,421,431$\rangle$; 7: $\langle$16,36,736$\rangle$;

  Which document(s) if any match each of the following queries, where each expression within quotes is a phrase query?
  1. ``fools rush in''
  2. ``fools rush in'' AND ``angels fear to tread''

• Consider the following fragment of a positional index with the format:

  word: document: $\langle$position, position, $\ldots\rangle$; document: $\langle$position, $\ldots\rangle$
  ...

  Gates: 1: $\langle$3$\rangle$; 2: $\langle$6$\rangle$; 3: $\langle$2,17$\rangle$; 4: $\langle$1$\rangle$;
  IBM: 4: $\langle$3$\rangle$; 7: $\langle$14$\rangle$;
  Microsoft: 1: $\langle$1$\rangle$; 2: $\langle$1,21$\rangle$; 3: $\langle$3$\rangle$; 5: $\langle$16,22,51$\rangle$;

  The /$k$ operator, word1 /$k$ word2 finds occurrences of word1 within $k$ words of word2 (on either side), where $k$ is a positive integer argument. Thus $k = 1$ demands that word1 be adjacent to word2.
  1. Describe the set of documents that satisfy the query Gates /2 Microsoft.
  2. Describe each set of values for $k$ for which the query Gates /$k$ Microsoft returns a different set of documents as the answer.

• Consider the general procedure for merging two positional postings lists for a given document, to determine the document positions where a document satisfies a /$k$ clause (in general there can be multiple positions at which each term occurs in a single document). We begin with a pointer to the position of occurrence of each term and move each pointer along the list of occurrences in the document, checking as we do so whether we have a hit for /$k$. Each move of either pointer counts as a step. Let $L$ denote the total number of occurrences of the two terms in the document. What is the big-O complexity of the merge procedure, if we wish to have postings including positions in the result?

• Consider the adaptation of the basic algorithm for intersection of two postings lists postings-merge-algorithm to the one in Figure 2.12 (page ), which handles proximity queries. A naive algorithm for this operation could be $O(P\dlenmax^2)$, where $P$ is the sum of the lengths of the postings lists (i.e., the sum of document frequencies) and $\dlenmax$ is the maximum length of a document (in tokens).
  1. Go through this algorithm carefully and explain how it works.
  2. What is the complexity of this algorithm? Justify your answer carefully.
  3. For certain queries and data distributions, would another algorithm be more efficient? What complexity does it have?

• Suppose we wish to use a postings intersection procedure to determine simply the list of documents that satisfy a /$k$ clause, rather than returning the list of positions, as in Figure 2.12 (page ). For simplicity, assume $k \ge 2$. Let $L$ denote the total number of occurrences of the two terms in the document collection (i.e., the sum of their collection frequencies). Which of the following is true? Justify your answer.
  1. The merge can be accomplished in a number of steps linear in $L$ and independent of $k$, and we can ensure that each pointer moves only to the right.
  2. The merge can be accomplished in a number of steps linear in $L$ and independent of $k$, but a pointer may be forced to move non-monotonically (i.e., to sometimes back up)
  3. The merge can require $kL$ steps in some cases.

• How could an IR system combine use of a positional index and use of stop words? What is the potential problem, and how could it be handled?