06 Index Compression

Question 1

Compression

Why do we compress dictionaries ?

Answer 1

• less disk space (=save money)
• keep more stuff in memory (=increase speed)
• increase speed of transfering data

Decompression algorithms are fast

Question 2

Compression

Lossy compression vs Lossless compression

Answer 2

• Lossy compression: discard some information (MP3, JPEG, some preprocessing steps)
• Lossless compression: all information is preserved

e.g. downcasing, stop words, stemming, number elimination

Question 3

Term statistics

What is Heaps’ Law ?

Answer 3

emperical laws that describe the growth of
the vocabulary (terms) in collections

M = kT^b given that 30 <= k <= 100, b = 0.5

Question 4

Term statistics

What is Zipf’s law ?

Answer 4

• describe the frequency of the vocabulary
• if the most frequent term (the) occurs cf1 times
  the second most frequent term (of) has half as many occurrences
  cf2 = 1/2 * cf1, cf3 = 1/3 * cf1

Few frequent terms, many rare terms

Question 5

Dictionary compression

Why are Fixed-width entries bad?

Answer 5

• most of the bytes in the term column are wasted
• cannot handle long words (too big for fixed-width)

Question 6

Dictionary compression

How does a dictionary as a string loook like?

Answer 6

store all of terms nect to each other and have pointers indicating word boundary

jump to positions using pointers (don’t have to read the whole string)

Question 7

Dictionary compression

How does a dictionary as a string
with blocking loook like?

Answer 7

• has fewer pointers
• have to go through a part of a string until the right position is found
• tradeoff: runtime

Question 8

Dictionary compression

What is front coding ?

Answer 8

store prefix once and store suffixes separately

Question 9

Postings compression

What is the main key of posting compression ?

Answer 9

we store gaps insted og docIDs

gaps will never be larger than docIDs

Question 10

Postings compression

Compute the VB code of 130

130(10) = 1000,0010(2)

Answer 10

0000 0001 1000 0010

Question 11

Compute the Gamma code of 130

130(10) = 1000,0010(2)

Answer 11

11111110 0000010

gamma code = length in unary code + offset

Question 12

what are properties of Gamma code ?

Answer 12

• prefix-free
• universal
• parameter-free

Question 13

What is more efficient? Why?

a) gamma code, b) variable byte encoding

Answer 13

b) variable byte encoding
* conceptually simpler
* VB is aligned (hardware works in byte level)