V.

3 Query Processing
1. Term-at-a-Time
2. Document-at-a-Time
3. WAND
4. Quit & Continue
5. Buckley’s Algorithm
6. Fagin’s Threshold Algorithms
7. Query Processing with Importance Scores
8. Query Processing with Champion Lists

Based on MRS Chapter 7 and RBY Chapter 9

IR&DM ’13/’14 !49
 Query Types
• Conjunctive
(i.e., all query terms are required)
• Disjunctive
(i.e., subset of query terms sufficient)
• Phrase or proximity
(i.e., query terms must occur in right order or close enough)
• Mixed-mode with negation
(e.g., “harry potter” review +movie -book)
• Combined with ranking of result documents according to
X
score(q, d) = score(t, d)
t2q

with score(t, d) depending on retrieval model (e.g., [Link],d)

IR&DM ’13/’14 !50

 Inverted Index

alf d123, 2, [4, 14] d133, 1, [47] d266, 3, [1, 9, 20]

ben d123, 2, [6, 22] d133, 1, [66] d268, 3, [1, 4, 23]

gil d567, 2, [7, 99] d136, 1, [22] d233, 3, [5, 12, 23]

willow d144, 2, [5, 19] d177, 1, [55] d244, 3, [7, 11,22]

yeast d234, 2, [8, 17] d299, 1, [26] d999, 3, [5, 66, 7]

zoo d888, 2, [7, 77] d889, 1, [23] d890, 3, [1, 9, 20]

• Document-ordered or score-ordered posting lists

• Posting lists with skip pointers allow for faster traversal

IR&DM ’13/’14 !51

 Overview of Query Processing Methods
• Holistic query processing methods determine whole query result
• Term-at-a-Time

• Document-at-a-Time

• Top-k query processing methods determine top-k query result

• WAND

• Quit & Continue

• Fagin’s Threshold Algorithms

• Opportunities for optimization over naïve merge & sort baseline

• skipping in document-ordered posting lists

• early termination of query processing for score-ordered posting lists

IR&DM ’13/’14 !52
 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 0.0

d4 : 0.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.0
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 0.0

d4 : 0.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.0
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 0.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.0
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 0.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.0
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 2.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.0
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 2.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.0
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 2.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.2
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 2.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.2
!
d8 : 0.0
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 2.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.2
!
d8 : 0.1
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 2.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.2
!
d8 : 0.1
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.2
!
d8 : 0.1
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 0.2
!
d8 : 0.1
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.1
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.1
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.0
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.1
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 3.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.1
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.1
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 2.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.1
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.1
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 1. Term-at-a-Time Query Processing
• Term-at-a-Time (TAAT) query processing
• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ successively

• maintains an accumulator for each result document with value

X
acc(d) = score(ti , d) after the first j posting lists have been read
ij
! Accumulators

! a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1 d1 : 1.0

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
!
d8 : 0.3
c d4, 3.0 d7, 1.0 d9 : 0.1
!

• required memory depends on the number of accumulators maintained

• top-k results can be determined by sorting accumulators at the end

IR&DM ’13/’14 !53

 Term-at-a-Time Query Processing
• Optimizations for conjunctive queries
• process query terms in ascending order of their document frequency
to keep the number of accumulators and thus required memory low

• for document-ordered posting lists, keep accumulators sorted

to make use of skip pointers when read posting lists

IR&DM ’13/’14 !54

 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

!
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
!
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
! d8 : 0.3
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
! d8 : 0.3
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
! d8 : 0.3
c d4, 3.0 d7, 1.0
!

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
! d8 : 0.3
c d4, 3.0 d7, 1.0
! d9 : 0.1

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 2. Document-at-a-Time Query Processing
• Document-at-a-Time (DAAT) query processing
• assumes document-ordered posting lists

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

! d1 : 1.0
a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1
d4 : 6.0
!
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1 d7 : 3.2
! d8 : 0.3
c d4, 3.0 d7, 1.0
! d9 : 0.1

• always advances posting list with lowest current document identifier

• required main memory depends on the number of results to be reported

• top-k results can be determined by keeping results in priority queue

IR&DM ’13/’14 !55
 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1

c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1

c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1

c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1

c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1

c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1

c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
d7 : 3.2
c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
d7 : 3.2
c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
d7 : 3.2
c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 Document-at-a-Time Query Processing
• Optimization for conjunctive queries using skip pointers
• when advancing posting list with lowest current document identifier,
advance to first posting having document identifier larger or equal to
max cdid(i)
i
where cdid(i) is the current document identifier in the i-th posting list

a d1, 1.0 d4, 2.0 d7, 0.2 d8, 0.1

d4 : 6.0
b d4, 1.0 d7, 2.0 d8, 0.2 d9, 0.1
d7 : 3.2
c d4, 3.0 d7, 1.0

IR&DM ’13/’14 !56

 3. WAND
• Weak AND (WAND) query processing
• assumes document-ordered posting lists with known maximum score
maxscore(i) of any posting in the i-th posting list

• reads posting lists for query terms ⟨ t1, …, t|q| ⟩ concurrently

• computes score when same document is seen in one or more posting lists

• always advances posting list with lowest current document identifier

up to pivot document identifier computed from current top-k result

• Computation of pivot document identifier

• let mink denote the lowest score in current top-k results

• sort posting lists in ascending order of cdid(i)

X
• pivot is cdid(j) of minimal j such that mink < maxscore(i)
ij
IR&DM ’13/’14 !57
 WAND
• Computation of pivot document identifier
• let mink denote the lowest score in current top-k results

• sort posting lists in ascending order of cdid(i)

X
• pivot is cdid(j) of minimal j such that mink < maxscore(i)
ij

Top-1
a d2, 0.5 d7, 0.1 d8, 0.2 d9, 0.6 d99, 1.0 d2 : 1.5
b d2, 0.5 d9, 0.3 d11, 0.2 d13, 0.1 d33, 1.0

c d2, 0.5 d3, 0.4 d4, 0.2 d5, 0.1 d57, 1.0
Pivot Computation

d3, 0.4 1.0 maxscore(i) = 1.0

d7, 0.1 2.0 d7 is pivot

d9, 0.3 3.0

IR&DM ’13/’14 !58

 WAND
• Intuition: No document with an identifier smaller than the pivot
can have a score large enough to make it into the top-k result

• Observation: As the value of mink can only increase over time,

WAND skips more and more postings as time progresses

• WAND can be made an approximate top-k query processing

method by computing the pivot such that
X
F ⇥ mink < maxscore(i)
ij

with tunable parameter F controlling fidelity of results

• Full details: [Broder et al. ’03]

IR&DM ’13/’14 !59
 4. Quit & Continue
• Quit & Continue query processing
• reads score-ordered posting lists for query terms ⟨ t1, …, t|q| ⟩
successively in descending order of idf(ti)

• Quit heuristics
• ignore posting lists for terms ti with idf(ti) below threshold

• stop scanning posting list for ti if tf(ti, dj)*idf(ti) drops below threshold

• stop scanning posting list when the number of accumulators is too high

• Continue heuristics
• upon reaching accumulator limit, continue reading remaining posting
lists, update existing accumulators but do not create new accumulators

• Full details: [Moffat and Zobel ’96]

IR&DM ’13/’14 !60
 5. Buckley’s Algorithm
• Buckley’s query processing method
• reads score-ordered posting lists concurrently in round-robin manner

• maintains partial scores of documents and keeps track of k-th best score

• computes upper bound for any unseen document based on current scores
X
ub = cscore(i)
i
with cscore(i) as the current score in the i-th posting list

• stops if upper bound ub is less than k-th best partial score

Top-1
a d2, 0.5 d1, 0.4 d5, 0.3 d9, 0.2 d2 : 1.0
b d2, 0.5 d3, 0.5 d61, 0.4 d13, 0.1

c d3, 0.4 d5, 0.3 d7, 0.2 d4, 0.1

ub = 0.9
IR&DM ’13/’14 !61
 Buckley’s Algorithm
• Note: This is a simplified version of Buckley’s algorithm. The
original algorithm maintains an upper bound for the (k + 1)-th
best document. If implemented correctly, this gives us the first
exact top-k query processing method described in the literature,
which is only based on sequential accesses.

• Full details: [Buckley and Lewitt ’85]

IR&DM ’13/’14 !62

 6. Fagin’s Threshold Algorithms
• Threshold Algorithm (TA)
• original version, often used as synonym for entire family of algorithms

• requires eager random access to candidate objects

• worst-case memory consumption: O(k)

• No-Random-Accesses (NRA)
• no random access required, may have to scan large parts of the lists

• worst-case memory consumption: O(m*n + k)

• Combined Algorithm (CA)

• cost-model for scheduling random accesses to candidate objects
• algorithmic skeleton very similar to NRA, but typically terminates faster

• worst-case memory consumption: O(m*n + k)

IR&DM ’13/’14 !63
 Fagin’s Threshold Algorithms
• Assume score-ordered posting lists
and additional index for score look-ups by document identifier
• Scan posting lists using inexpensive sequential accesses (SA)
in round-robin manner
• Perform expensive random accesses (RA) to look up scores for
a specific document when beneficial
• Support monotone score aggregation function
aggr : Rm ! R : 8xi x0i ) aggr(x1 , . . . , xm ) aggr(x01 , . . . , x0m )

• Compute aggregate scores incrementally in candidate queue

• Compute score bounds for candidate results and
stop when threshold test guarantees correct top-k result

IR&DM ’13/’14 !64

 Threshold Algorithm (TA)
• Sequential accesses (SA) Threshold Algorithm (TA):
scan index lists (e.g., round-robin)
mixed with eager random consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
accesses (RA) !
if d ∉ top-k then // compute score(d)
• Worst-case memory look up score(tj, d) for all j ≠ i
score(d) = aggr{ score(tj, d) | j = 1 … |q| }
consumption O(k) !
if score(d) > min-k then // update top-k
add d to top-k and remove min-score d’
mink = min{ score(d’) | d’ ∈ top-k }
!
ub = aggr{high(i) | i = 1 … |q|} // update upper bound
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 Top-2

b d64, 0.9 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1

c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
SA RA

IR&DM ’13/’14 !65

 Threshold Algorithm (TA)
• Sequential accesses (SA) Threshold Algorithm (TA):
scan index lists (e.g., round-robin)
mixed with eager random consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
accesses (RA) !
if d ∉ top-k then // compute score(d)
• Worst-case memory look up score(tj, d) for all j ≠ i
score(d) = aggr{ score(tj, d) | j = 1 … |q| }
consumption O(k) !
if score(d) > min-k then // update top-k
add d to top-k and remove min-score d’
mink = min{ score(d’) | d’ ∈ top-k }
!
ub = aggr{high(i) | i = 1 … |q|} // update upper bound
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 Top-2

b d10 : 2.1
d64, 0.9 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1
d78 : 1.5
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
ub = 2.5 SA RA

IR&DM ’13/’14 !65

 Threshold Algorithm (TA)
• Sequential accesses (SA) Threshold Algorithm (TA):
scan index lists (e.g., round-robin)
mixed with eager random consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
accesses (RA) !
if d ∉ top-k then // compute score(d)
• Worst-case memory look up score(tj, d) for all j ≠ i
score(d) = aggr{ score(tj, d) | j = 1 … |q| }
consumption O(k) !
if score(d) > min-k then // update top-k
add d to top-k and remove min-score d’
mink = min{ score(d’) | d’ ∈ top-k }
!
ub = aggr{high(i) | i = 1 … |q|} // update upper bound
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 Top-2

b d10 : 2.1
d64, 0.9 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1
d78 : 1.5
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
ub = 1.9 SA RA

IR&DM ’13/’14 !65

 Threshold Algorithm (TA)
• Sequential accesses (SA) Threshold Algorithm (TA):
scan index lists (e.g., round-robin)
mixed with eager random consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
accesses (RA) !
if d ∉ top-k then // compute score(d)
• Worst-case memory look up score(tj, d) for all j ≠ i
score(d) = aggr{ score(tj, d) | j = 1 … |q| }
consumption O(k) !
if score(d) > min-k then // update top-k
add d to top-k and remove min-score d’
mink = min{ score(d’) | d’ ∈ top-k }
!
ub = aggr{high(i) | i = 1 … |q|} // update upper bound
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 Top-2

b d10 : 2.1
d64, 0.9 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1
d78 : 1.5
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
ub = 1.7 SA RA

IR&DM ’13/’14 !65

 Threshold Algorithm (TA)
• Sequential accesses (SA) Threshold Algorithm (TA):
scan index lists (e.g., round-robin)
mixed with eager random consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
accesses (RA) !
if d ∉ top-k then // compute score(d)
• Worst-case memory look up score(tj, d) for all j ≠ i
score(d) = aggr{ score(tj, d) | j = 1 … |q| }
consumption O(k) !
if score(d) > min-k then // update top-k
add d to top-k and remove min-score d’
mink = min{ score(d’) | d’ ∈ top-k }
!
ub = aggr{high(i) | i = 1 … |q|} // update upper bound
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 Top-2

b d10 : 2.1
d64, 0.9 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1
d78 : 1.5
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
ub = 1.1 SA RA

IR&DM ’13/’14 !65

 Threshold Algorithm (TA)
• Sequential accesses (SA) Threshold Algorithm (TA):
scan index lists (e.g., round-robin)
mixed with eager random consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
accesses (RA) !
if d ∉ top-k then // compute score(d)
• Worst-case memory look up score(tj, d) for all j ≠ i
score(d) = aggr{ score(tj, d) | j = 1 … |q| }
consumption O(k) !
if score(d) > min-k then // update top-k
add d to top-k and remove min-score d’
mink = min{ score(d’) | d’ ∈ top-k }
!
ub = aggr{high(i) | i = 1 … |q|} // update upper bound
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 Top-2
d10 : 2.1

ST
b d64, 0.9 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1

O
d78 : 1.5

P!
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
ub = 1.1 SA RA

IR&DM ’13/’14 !65

 No-Random-Accesses Algorithm (NRA)
• Sequential accesses No-Random-Accesses Algorithm (NRA):
scan index lists (e.g., round-robin)
(SA) only consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
eval(d) = eval(d) ∪ {i} // where have we seen d?
• Worst-case memory !
consumption O(m*n + k) worst(d) = aggr{ score(tj, d) | j ∈ eval(d) }
best(d) = aggr{ worst(d), aggr{ high(j) | j ∉ eval(d) } }
!
if worst(d) > mink then // good enough for top-k?
add d top top-k
mink = min{ worst(d’) | d’ ∈ top-k }
else if best(d) > mink then // good enough for cand?
cand = cand ∪ { d }
ub = max{ best(d’) | d’ ∈ cand }
if ub ≤ mink then
exit

a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2

b d64, 0.8 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
SA RA

IR&DM ’13/’14 !66

 No-Random-Accesses Algorithm (NRA)
• Sequential accesses No-Random-Accesses Algorithm (NRA):
scan index lists (e.g., round-robin)
(SA) only consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
eval(d) = eval(d) ∪ {i} // where have we seen d?
• Worst-case memory !
consumption O(m*n + k) worst(d) = aggr{ score(tj, d) | j ∈ eval(d) }
best(d) = aggr{ worst(d), aggr{ high(j) | j ∉ eval(d) } }
!
if worst(d) > mink then // good enough for top-k?
add d top top-k
mink = min{ worst(d’) | d’ ∈ top-k }
else if best(d) > mink then // good enough for cand?
cand = cand ∪ { d }
ub = max{ best(d’) | d’ ∈ cand }
if ub ≤ mink then
exit
worst best
a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 d78 : 0.9 : 2.4 Top-1
d64 : 0.8 : 2.4
b d64, 0.8 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1 d10 : 0.7 : 2.4
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1
ub = 2.4 SA RA

IR&DM ’13/’14 !66

 No-Random-Accesses Algorithm (NRA)
• Sequential accesses No-Random-Accesses Algorithm (NRA):
scan index lists (e.g., round-robin)
(SA) only consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
eval(d) = eval(d) ∪ {i} // where have we seen d?
• Worst-case memory !
consumption O(m*n + k) worst(d) = aggr{ score(tj, d) | j ∈ eval(d) }
best(d) = aggr{ worst(d), aggr{ high(j) | j ∉ eval(d) } }
!
if worst(d) > mink then // good enough for top-k?
add d top top-k
mink = min{ worst(d’) | d’ ∈ top-k }
else if best(d) > mink then // good enough for cand?
cand = cand ∪ { d }
ub = max{ best(d’) | d’ ∈ cand }
if ub ≤ mink then
exit
worst best
a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 d78 : 1.4 : 2.0 Top-1
d23 : 1.4 : 1.9
b d64, 0.8 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1 d64 : 0.8 : 2.1
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1 d10 : 0.7 : 2.1

ub = 2.1 SA RA

IR&DM ’13/’14 !66

 No-Random-Accesses Algorithm (NRA)
• Sequential accesses No-Random-Accesses Algorithm (NRA):
scan index lists (e.g., round-robin)
(SA) only consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
eval(d) = eval(d) ∪ {i} // where have we seen d?
• Worst-case memory !
consumption O(m*n + k) worst(d) = aggr{ score(tj, d) | j ∈ eval(d) }
best(d) = aggr{ worst(d), aggr{ high(j) | j ∉ eval(d) } }
!
if worst(d) > mink then // good enough for top-k?
add d top top-k
mink = min{ worst(d’) | d’ ∈ top-k }
else if best(d) > mink then // good enough for cand?
cand = cand ∪ { d }
ub = max{ best(d’) | d’ ∈ cand }
if ub ≤ mink then
exit
worst best
a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 d10 : 2.1 : 2.1 Top-1
d78 : 1.4 : 2.0
b d64, 0.8 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1 d23 : 1.4 : 1.7
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1 d64 : 1.1 : 1.9

ub = 2.0 SA RA

IR&DM ’13/’14 !66

 No-Random-Accesses Algorithm (NRA)
• Sequential accesses No-Random-Accesses Algorithm (NRA):
scan index lists (e.g., round-robin)
(SA) only consider d = cdid(i) in posting list for ti
high(i) = cscore(i)
eval(d) = eval(d) ∪ {i} // where have we seen d?
• Worst-case memory !
consumption O(m*n + k) worst(d) = aggr{ score(tj, d) | j ∈ eval(d) }
best(d) = aggr{ worst(d), aggr{ high(j) | j ∉ eval(d) } }
!
if worst(d) > mink then // good enough for top-k?
add d top top-k
mink = min{ worst(d’) | d’ ∈ top-k }
else if best(d) > mink then // good enough for cand?
cand = cand ∪ { d }
ub = max{ best(d’) | d’ ∈ cand }
if ub ≤ mink then
exit
worst best
a d78, 0.9 d23, 0.8 d10, 0.8 d1, 0.7 d88, 0.2 d10 : 2.1 : 2.1 Top-1
d78 : 1.4 : 2.0

ST
b d64, 0.8 d23, 0.6 d10, 0.6 d12, 0.2 d78, 0.1 d23 : 1.4 : 1.7
O
P!
c d10, 0.7 d78, 0.5 d64, 0.3 d99, 0.2 d34, 0.1 d64 : 1.1 : 1.9

ub = 2.0 SA RA

IR&DM ’13/’14 !66

 Combined Algorithm (CA)
• Balanced SA/RA Scheduling:
• define cost ratio r = CSA/CRA (e.g., based on statistics for execution
environment, typical values CRA/CSA ~ 100 - 10,000 for hard disks)

• run NRA (using SA only) but perform one RA every r rounds

(i.e., m*r SAs) to look up the unknown scores of the best candidate
that is not in the current top-k

• Cost competitiveness w.r.t. “optimal schedule”

(scan until aggr{ high(i) } ≤ min{ best(d) | d ∈ final top-k },
then perform RAs for all d’ with best(d’) > mink): 4*m + k

IR&DM ’13/’14 !67

 TA / NRA / CA Instance Optimality
• Definition: For class of algorithms A and class of datasets D,
algorithm A ∈ A is instance optimal over A and D if
8A0 2 A 8D 2 D : cost(A, D)  c · cost(A0 , D) + c0
(i.e., cost(A, D) 2 O(cost(A0 , D)))
• TA is instance optimal over all top-k algorithms based on
random and sequential accesses to m lists (no “wild guesses”)
• NRA is instance optimal over all top-k algorithms based on
only sequential accesses
• CA is instance optimal over all top-k algorithms based on
random and sequential accesses and given cost ratio CRA/CSA
• Full details: [Fagin et al. ’03]

IR&DM ’13/’14 !68

 Implementation Issues for Threshold Algorithms
• Limitation of asymptotic complexity
• m (# lists), n (# documents), k (# results) are important parameters

• Priority queues
• straightforward use of heap (even Fibonacci) has high overhead

• better: periodic rebuilding of queue with partial sort O(n log k)

• Memory management
• peak memory usage as important for performance as scan depth

• aim for early candidate pruning even if scan depth stays the same

IR&DM ’13/’14 !69

 7. Query Processing with Importance Scores
• Focus on score combining textual relevance (rel) (e.g., TF*IDF)
and global importance (imp) (e.g., PageRank)
score(q, d) = imp(d) + rel(q, d)
with normalization imp(d) ≤ a and rel(q, d) ≤ b and a + b ≤ 1
• Keep posting lists in descending order of global importance
high(i) = imp(cdid(i)) + b // upper bound for document from i-th list
high = max{ high(i) | i = 1 … |q| } + b // global upper bound
Stop scanning i-th posting list when high(i) < mink (i.e., minimal score in top-k)
Terminate when high < mink

effective when combined score is dominated by imp(d)

• First-k’ heuristic: Scan all posting lists until k’ ≥ k documents
have been seen in all lists, so that their combined score is known
• Full details: [Long and Suel ’03]
IR&DM ’13/’14 !70
 8. Query Processing with Champion Lists
• Idea: In addition to full posting lists Li sorted by imp(d),
keep short “champion lists” sorted (aka. “fancy lists”) Fi
that contain docs d with the highest values of score(ti, d)
and sort these lists by imp(d)
• Champions First-k’ heuristic:
Compute total score for all docs in ∩ Fi (i = 1 … |q|) and keep top-k results
cand = ∪ Fi - ∩ Fi
for each d ∈ cand do
compute partial score of d

scan full posting lists Li (i = 1 … |q|)

if cdid(i) ∈ cand then
add score(ti, cdid(i)) to partial score of cdid(i)
else
add cdid(i) to cand and set its partial score to score(ti, cdid(i))
terminate the scan when we have k’ documents with complete scores

• Full details: [Brin and Page ’98]

IR&DM ’13/’14 !71
 Summary of V.3
• Query Type
determines usefulness of optimizations (e.g., skip pointers)
• Term-at-a-Time and Document-at-a-Time
for holistic query processing
• WAND
for top-k query processing on document-ordered posting lists
• Buckley’s Algorithm
for top-k query processing on scored-ordered posting lists
• Fagin’s Threshold Algorithms
top-k query processing with, without, or with some RAs

IR&DM ’13/’14 !72

 Additional Literature for V.3
• S. Brin and L. Page: The anatomy of a large-scale hypertextual Web search engine,
Computer Networks 30:107-117, 1998

• A. Broder, D. Carmel, M. Herscovici, A. Soffer, J. Zien: Efficient query evaluation

using a two-level retrieval process, CIKM 2003

• C. Buckley and A. Lewit: Optimization of Inverted Vector Searches,

SIGIR 1985

• R. Fagin, A. Lotem, and M. Naor: Optimal Aggregation Algorithms for Middleware,

Journal of Computer and System Sciences 2003

• X. Long and T. Suel: Optimized Query Execution in Large Search Engines with Global
Page Ordering, VLDB 2003

• J. Zobel and A. Moffat: Self-Indexing Inverted Files for Fast Text Retrieval,
ACM TOIS 14(4):349-379, 1996

IR&DM ’13/’14 !73