Advanced Indexing

Question 1

What is the difference between a term-partitioned and a document-partitioned index?

Answer 1

For term-partitioned, one machine handles a subrange of terms
For document-partitioned, one machine handles a subrange of documents

Question 2

What is the simplest approach to dynamic indexing to handle inserts?

Answer 2

For insert, maintain a main index on disk. New docs go to an auxiliary index in memory. Search across both then merge results

Question 3

What is the simplest approach to dynamic indexing to handle deletes?

Answer 3

Use an invalidation bit-vector for deleted docs. Filter searches using this bit vector

Question 4

What is the issue with using a main and auxiliary index?

Answer 4

1. The problem of frequent merges
2. Poor performance during merge
3. Collection-wide statistics are hard to maintain

Question 5

How can we make the main and auxiliary index approach more efficient?

Answer 5

Merging is made efficient if we keep a separate file for each postings list as we would then just need to append the lists together.
However, we then need a lot of files which is inefficient for the OS

Question 6

What are some reasons for using file compression?

Answer 6

1. Uses less disk space
2. Able to keep more stuff in memory
3. Increase speed of data transfer from disk to memory

Question 7

Why should we use file compression for a dictionary structure?

Answer 7

1. Allows us to keep it small enough to fit in main memory
2. Small enough to keep some postings lists in main memory as well

Question 8

How do we solve the size issue of a postings list using gap encoding?

Answer 8

Instead of recording the docID of every document in the postings list, we instead record the size of the gap between doc IDs where the term appears. The hope is that gaps can be encoded with fewer bits than the doc IDs

Question 9

How can we use gamma codes for gap encoding?

Answer 9

1. Represent a gap as a length and offset
2. The offset is the gap in binary with the leading bit cut off
3. Length is the length of offset
4. Encode length as a unary code
5. Concatenate the length and offset

Question 10

Show how 13 is gamma encoded

Answer 10

1. Offset: 13 -> 1101 -> 101
2. Length: 3 -> 1110
3. Output: 1110101