Query processing:
phrase queries and positional indexes
Paolo Ferragina
Dipartimento di Informatica Università di Pisa
Phrase queries
Want to be able to answer queries such as
“ stanford university” – as a phrase
Thus the sentence “ I went at Stanford my university” is not a match.
Solution #1: 2-word indexes
For example the text “ Friends, Romans, Countrymen” would generate the biwords
friends romans
romans countrymen
Each of these 2-words is now an entry in the dictionary
Two-word phrase query-processing is immediate.
Sec. 2.4.1
Longer phrase queries
Longer phrases are processed by reducing them to bi-word queries in AND
stanford university palo alto can be broken into the Boolean query on biwords, such as
stanford university AND university palo AND palo alto
Need the docs to verify +
They are combined with other solutions
Can have false positives!
Index blows up
Solution #2: Positional indexes
In the postings, store for each term and document the position(s) in which that term occurs:
<term, number of docs containing term;
doc1: position1, position2 … ; doc2: position1, position2 … ; etc.>
Sec. 2.4.2
Processing a phrase query
“ to be or not to be” .
to:
2:1,17,74,222,551; 4:8,16,190,429,433;
7:13,23,191; ...
be:
1:17,19; 4:17,191,291,430,434;
5:14,19,101; ...
Same general method for proximity searches
Query term proximity
Free text queries: just a set of terms typed into the query box – common on the web
Users prefer docs in which query terms occur within close proximity of each other
Would like scoring function to take this into account – how?
Sec. 7.2.2
Positional index size
You can compress position values/offsets
Nevertheless, a positional index expands postings storage by a factor 2-4 in English
Nevertheless, a positional index is now
commonly used because of the power and usefulness of phrase and proximity queries
… whether used explicitly or implicitly in a ranking retrieval system.
Combination schemes
2-Word + Positional index is a profitable combination
2-word is particularly useful for particular phrases (“ Michael Jackson” , “ Britney Spears” )
More complicated mixing strategies do exist!
Sec. 2.4.3
Soft-AND
E.g. query rising interest rates
Run the query as a phrase query
If <K docs contain the phrase rising interest
rates, run the two phrase queries rising interest and interest rates
If we still have <K docs, run the “ vector space query” rising interest rates (…see next…)
“Rank” the matching docs (…see next…)
Zone indexes
Paolo Ferragina
Dipartimento di Informatica Università di Pisa
Parametric and zone indexes
Thus far, a doc has been a term sequence
But documents have multiple parts:
Author
Title
Date of publication
Language
Format
etc.
These are the metadata about a document
Zone
A zone is a region of the doc that can contain an arbitrary amount of text e.g.,
Title
Abstract
References …
Build inverted indexes on fields AND zones to permit querying
E.g., “ find docs with merchant in the title zone and matching the query gentle rain”
Sec. 6.1
Example zone indexes
Encode zones in dictionary vs. postings.
Caching for faster query
Two opposite approaches:
I. Cache the query results (exploits query locality)
II. Cache pages of posting lists (exploits term locality)
Tiered indexes for faster query
Break postings up into a hierarchy of lists
Most important
…
Least important
Inverted index thus broken up into tiers of decreasing importance
At query time use top tier unless it fails to yield K docs
If so drop to lower tiers
Example tiered index
Sec. 7.2.1
Skip pointers (at indexing time)
How do we deploy them ?
Where do we place them ?
128
2 4 8 41 48 64
31
1 2 3 8 11 17 21
11 31
41 128
Sec. 2.3
Using skips
128
2 4 8 41 48 64
31
1 2 3 8 11 17 21
11 31
41 128
Suppose we’ ve stepped through the lists until we process 8 on each list. We match it and advance.
We then have 41 and 11 on the lower. 11 is smaller.
But the skip successor of 11 on the lower list is 31, so we can skip ahead past the intervening postings.
Placing skips
Tradeoff:
More skips shorter spans more likely to skip. But lots of comparisons to skip
pointers.
Fewer skips longer spans few
successful skips. Less pointer comparisons.
Sec. 2.3
Placing skips
Simple heuristic for postings of length L
use L evenly-spaced skip pointers.
This ignores the distribution of query terms.
Easy if the index is relatively static.
This definitely useful for in-memory index
The I/O cost of loading a bigger list can outweigh the gains!
Placing skips, contd
What if it is known a distribution of accesses pk to the k-th element of the inverted list?
w(i,j) = sumk=i..j pk [prob access an item in pos i..j]
L^0(i,j) = average cost of accessing an item in the sublist from i to j = sumk=i..j pk * (k-i+1)
L^1(1,n) = average cost with one single skip 1 (first skip cmp) + (avg cost access the two lists)
minu>1 w(1,u-1) * L^0(1,u-1) + w(u,n) * L^1(u,n)
L^0(i,j) can be tabulated in O(n^2) time
Computing L^1(i,n) takes O(n), given L^1(j,n), for j>i
Computing the total L^1(1,n) takes O(n^2) time
Sec. 2.3
You can solve it by Shortest Path
Placing skips, contd
What if it is also fixed the maximum number of skip-pointers that can be allocated?
Same as before but we add the parameter p
L^1_p(1,n) = 1 + min_{u>1} w(1,u-1) * L^0(1,u-1) +
w(u,n) * L^1_{p-1}(u,n)
L^1_0(i,j) = L^0(i,j), i.e. no pointers left, so scan
L^1_i(j,n) takes O(n) time [min calculation] if are available the values for L^{i-1}(h,n) with h > j
So L^p(1,n) takes O(n^2) time for a fixed p
Auto-completion Search
What’s the dictionary ?
Top-1
What’s the ranking/scoring of the answers ?
1
2 2
0
4
5
6
7
2 3
y
s
1 z
stile zyg
5 etic
ial ygy
aibelyite
czecin omo
P = sy
8
2 1 4
8,1
How to compute the top-1 in O(1) time ?
1
2 2
0
4
5
6
7
2 3
y
s
1 z
stile zyg
5 etic
ial ygy
aibelyite
czecin omo
P = sy
8
2 1 4
4
1 7
2
3
5
8,1
1Top-2
How to compute the top-2 in O(1) time ?
1
2 2
0
4
5
6
7
2 3
y
s
1 z
stile zyg
5 etic
ial ygy
aibelyite
czecin omo
P = sy
8
2 1 4
4,2
1,4 7,6
2
3
5 1,7
Top-k in O(1) time, but k× space
1
2 2
4
5
6
7
2 3
y
s
1 z
stile zyg
5 etic
ial ygy
aibelyite
czecin omo
P = sy
8
2 1 4
2
3
5
8 1
2 2
1 3
4 4
2 5
3 6
5 7 Score
String
Prefixed by P, proceed D&C
Top-k: How to squeeze ?
8 1
2 2
1 3
4 4
2 5
3 6
5 7 Score
String
Prefixed by P, proceed D&C
Let H be a max-heap of size k, keep also min[H] and max[H]
Initialize H with k pairs <-, NULL>
Given the range <L,R> (here <1,4>)
Compute max-score in Array[L,R] (pos. M, value m)
If m ≤ min[H], skip;
else:
Insert <m,string> in H;
If size(H)>k then remove min[H];
Recurse on <L,M-1> and <M+1,R>, if not empty.
Time: O(k) time, and space
L R RMQ-query
in O(1) time and O(n) space
Depth-first visit of the possibilities, it might find bad results first
4 1
2 2
1 3
8 4
2 5
3 6
5 7 Score
String
Consider this other array
Range : operations
[1,7]: H <8,4>; recurse on [1,3] and [5,7]
[1,3]: H={<8,4>} <4,1>; recurse on [1,0] and [2,3]
[5,7]: H={<8,4>,<4,1>} <5,7>; delete <4,1> from H, recurse on [5,6] and [8,7]
[2,3]: H={<8,4>,<5,7>} <2,2>; since min[H]=5, not insert in H [5,6]: H ={<8,4>,<5,7>} <3,6>; since min[H]=5, not insert in H
H = {<8,4> e <5,7>}
L R
A smarter approach
8 1
2 2
1 3
4 4
2 5
3 6
5 7 Score
String
Prefixed by P, proceed D&C
Let H be a max-heap, including items <val, string, [low,high]>
Compute max-score in Array[L,R] (pos. M, value m) i=0; insert <m, string[M], L, R> in H
While (i<k) do
Extract <x, string[X], Lx, Rx> from H, where x is max-value in H
Return String[X] as one of the top-k strings
Compute max-score in Array[Lx,X-1] (pos. M’, value m’)
insert <m’, string[M’], Lx, X-1>
Compute max-score in Array[X+1,Rx] (pos. M’’, value m’’)
insert <m’’, string[M’’], X+1, Rx>
i++;
Time: still O(k) time, and space
L R
