03 English Terms, Skip Pointers, Phrase Queries, Dictionaries

Question 1

How do skip pointers improve the performance?

Answer 1

• makes intersecting postings lists more efficient
• by skip postings that will not figure in the search results

Question 2

Whate is the tradeoff of placing more and fewer skips?

Answer 2

Tradeoff:
number of items skipped vs. frequency skip can be taken
More: skips only a few items, but we can frequently use it
Fewer: skips many items, but we can not use it very often.

Question 3

Where do we place skips?

Answer 3

Simple heuristic: for postings list of length P, use √P evenly-spaced skip pointers.

Question 4

Is there a case where skip pointers are not helpful?

Answer 4

Easy if the index is static; harder in a dynamic environment because of updates.

Question 5

How much do skip pointers help?

Answer 5

Memory/Computation tradeoff

Question 6

How do we deal with phrase query?

Answer 6

• biword index (phrase index)
• positional index

Question 7

How to extend inverted index into biword index?

Answer 7

Index every consecutive pair of terms

Friends, Romans, Countrymen:
“friends romans” and “romans countrymen”

Question 8

How do we deal with phrase with more than two words?

Answer 8

“stanford university palo alto” can be
represented as the Boolean query

“stanford university” AND “university palo” AND “palo alto”

Question 9

Why are biword indexes rarely used?

Answer 9

• False positives
• Index blowup due to very large term vocabulary

Question 10

What are positional index?

Answer 10

Inverted index but each posting is a docID and a list of positions

however, it is more expensive than regular boolean queries

Question 11

What is proximity search?

Answer 11

use the positional index to for phrase search
where we can find documents contain w1 and w2
within n words from each other

Question 12

How do positional index work?

Answer 12

run the intersection algorithm twice, 1) docID 2) position

Question 13

What are pos an con of proximity search?

Answer 13

Pos: important for dynamic summaries
Con: inefficeint for frequent words

Question 14

In what case where biwords are efficient?

Answer 14

• when used with extremely frequent biword (e.g., Britney Spears)

Question 15

What is combination scheme?

Answer 15

• a combination of biword indexes and positional indexes
• include frequent biwords as vocabulary terms in the index

Question 16

Which data structure do we use to locate the entry (row)
in the array where q (a query term) is stored?

(assume that we store term vocabulary in fixed-length)

Answer 16

• hashes
• trees

Question 17

What are pros and cons for hashes?

Answer 17

Pros:
* faster than tree
* looking up time is consistant (assuming no collision)

Con:
* can not find variants (resume vs. r´esum´e)
* lookup time could be higher depending on hash functions
* no prefix search

Question 18

What problem does tree structure fix?

Answer 18

the prefix problem

but slightly slower than in hashes

Question 19

What is casefolding?

Answer 19

reduce all letters to lower case

often best to lowercase everything

Question 20

What are stopwords?

Answer 20

extremely common words which would appear to be of little value in helping select documents matching a user need

a case where we need stopwords : “King of Denmark”

Question 21

What is lemmatization?

Answer 21

Reduce inflectional/variant forms to base form

Question 22

What is stemming?

Answer 22

Crudely chops off
the ends of words

Question 23

Name 3 stemmers

Answer 23

1. Porter stemmer
2. Lovins stemmer
3. Paice stemmer

Question 24

What is SoundEx?

Answer 24

the basis for finding phonetic
(as opposed to orthographic) alternatives