C3: Boolean model and index construction

Question 1

term-document incidence matrix

Answer 1

rows are terms, columns are document, a 1 indicates the occurrence of that term in the document

But this explodes in size for many documents and the matrix is sparse => better to only record non-zero positions

Question 2

inverted index

Answer 2

for each term, store a list of all documents that contain it (postings)

Question 3

evaluation of a Boolean IR system

Answer 3

Boolean model does not perform ranking

precision: fraction of retrieved documents relevant to the user’s information need

recall: fraction of relevant documents in the collection that are retrieved

Question 4

disadvantages of Boolean retrieval

Answer 4

• based on binary decision criteria with no notion of partial matching
• no ranking of the documents
• information need has to be translated into a Boolean expression

Question 5

positional indexes

Answer 5

Useful if we want to match phrases (New York University)

in the postings, store for each term the positions in which tokens of it appear

Question 6

Zipf’s law

Answer 6

while only a few words are used very often, many are used rarely

if words are ranked by their frequency, the product of the rank number and frequency make up a constant: the k-th most frequent term has a frequency proportional to 1/k

Question 7

Huffman coding

Answer 7

1. Create a leaf node for each symbol and add it to the
   priority queue.
2. While there is more than one node in queue:
   
   1. Remove two nodes of lowest probability from queue
   2. Create new internal node with these two nodes as children => new frequency is sum of the two nodes’ frequencies
   3. Add new node to queue

Question 8

entropy

Answer 8

minimum number of bits per symbol for lossless encoding
H(P) = - sum P(x) log P(x)

Question 9

why would we want index compression?

Answer 9

• inverted lists are very large
• compression of indexes saves disk and memory space
• best compression techniques have good compression ratios and are easy to decompress

Question 10

delta encoding

Answer 10

encode differences between document numbers (gaps): differences for high-frequency words are easier to compress and differences for low-frequency words are large

most gaps can be encoded with far fewer than 20 bits

Question 11

variable length encoding

Answer 11

encode every gap integer with as few bits as needed: use the first bit of a byte as continuation bit, to indicate if the value continues in the next byte or not (7 bits left for encoding)