Vl 4 Boolean Retrieval

Question 1

Boolean Retrieval

Answer 1

• queries are boolean expressions
• search enginge returns all documents that satisfy the expression

Question 2

Term-Document Incidence Matrix

Answer 2

• rows = documents
• columns = terms
• entrance = 1 or 0
• memory overhead

Question 3

Incidence Vector

Answer 3

• vector for each term
• column

Question 4

Inverted Index

Answer 4

• for each term a list of all documents are store, where the term appears
• singly linked list, sorted by document ID
• dictionary kept in memory (smaller)
• postin kept in background storage (larger)

Question 5

Simple conjunctive query

Answer 5

• locate the terms
• retrieve posting lists from the file
• intersect the two posting lists
• step by step comparision

Question 6

Query optimization

Answer 6

• start with shortest posting list (document frequency)
• AND two posting list

Question 7

Skip pointer

Answer 7

• allow us to skip ostings in the list
• intersectiong list more efficient
• problem: where to put pointers
• sqrt(P) pointers (P = length of posting list)

Question 8

Hierachical organization

Answer 8

• multiple skip pointers at a posting

Question 9

Phrase queries

Answer 9

• words that belong together

Question 10

(Phrase queries)
Bi-Word indexes

Answer 10

• index evey consecutive pair of terms in the text as a phrase -> new vocabulary term
• memory
• false positives -> post- filtering

Question 11

(Phrase queries)
Extended Bi-Words

Answer 11

• perform part-of-speech tagging for each document
• bucket terms into nouns N or articles/prepositions X
• terms of the form NX*N are extended Bi-words
• false positives
• index blow-up

Question 12

(Phrase queries)
Position index

Answer 12

• each posting is a doc-ID and a ist of positions (in a document)
• used for proximity search

Question 13

combination scheme

Answer 13

• bi-word indexes and positionale indexes
• include frequent bi-words as vocabulary terms
• individual words common, desired phrases is rare