Exercise 1.12

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.

My Answer:

分为了 New York AND York University，显然 New York University 是一个特定的词组，前面的查询肯定会返回错误的结果。

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$;

Exercise 1.13

Which document(s) if any match each of the following queries, where each expression within quotes is a phrase query?

fools rush in
fools rush in AND angels fear to tread

My Answer:

先处理第一个查询，这里还要考虑单词出现的顺序满足 fools 第一，之后是 rush，最后是 in。这里 doc2 和 doc4，doc7都满足。

接着看第二个查询，AND 右边的部分得到 doc4，所以整个的结果就是 doc4。

Exercise 1.14

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.

My Answer:

第一问，根据定义，doc1 和 doc3 都满足。

第二问，见如下表格：

Exercise 1.15

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?

Exercise 1.16

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 \ L_{max}^2)$, where $P$ is the sum of the lengths of the postings lists (i.e., the sum of document frequencies) and $L_{max}$ 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?

Exercise 1.17

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.

Exercise 1.18

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?