HH2EHH:
sheet  l  j l I uco  c I .L-j i—- J—t l I U L points
Recommend a query processing strategy [2 points] for the following boolean query: (Cleopatra OR Calpurnia) AND (Brutus OR Caesar)
given the following document frequencies:
• Cleopatra: 21,502 documents
• Calpurnia: 257,219 documents
• Brutus: 163,587 documents
• Caesar: 175,843 documents
Several strategies for estimating the cardinality of the result for an "OR" query exist. Explain which one you used and what assumption your strategy makes. [2 points]
1 CL£o?ATRft    OR.   CALfUKNlR \ = | CLE(7PATRft | + ICftLPUKMI^ \ ftsscAV^VuM•'  HfcctAwe^b  6>hUV\i4<j    CL&ofATKA CAlPURM|f\
are
1 Brutus I + IcaesmU =333 HIO Aocs
( aCOfATRA   OR  CALPURNIA*) AKJJ>   ( IkVTVS   OR CfttfhK.*)
\cizor(\T?.f\  or Cf\l?o*KJiA\ - rmx ( UleopatrM t |cAipoRNih() ftsswvM^o^ : 3>0Cfcuue/nts:   a>*UWivv^   CLE0PftTRfi  a/*** CAlp(jRN(fl
mAxdat^PfMRftl, icAi-puiuim^ = zsi 219 <ws
or £A£SA|0)   ftNp   (CLfoPATRPi   OR CAlH>RN(ft)
Write your solution only on this side of the sheet!
DDD1 E
I     f   r.    ,1 r.    ,n   r,     ,1   r, ,1
mco  l- I     . J—j J—I L- 'j i-4 l 'j points
Perform the following boolean query: Friends AND Romans
given the following inverted index:___
• Friends: ^%1^23^39^to, 41,47, 49,51 ~*   L^TftJ " 3
• Romans: 2,3,5,7^1X^29,31,37,39^41^43^47 |p|=       /o> = 3
Present the result of the query and the number of comparisons with [2 points], and without [2 points] a skip list. Assume the skip list has frequency LvT^IJ' where |P| is the cardinality of a posting P
and [-J is the floor function. (Example: P = {1,2,3}, \P\ = 3, sf\F\ « 1.73, {^J\P\\ = 1)
- vx/itlooiAt   4  skip   list :   % u>myAUSov\s
(35,291, (S3,31\ (33,3^, (3^33) , (*tl) , (11, Hi),
- \X/itlo   a.   skip :   /fg C0*>$ar\>oY\S
(3,2), (J,^, (^(j^), (3,1)( (9,29){ (9,11) , flS,1l\ U^, 13), (10,23), (23,23^ (39,23), (35,^), (lO, <n) ( lH3,m), (H1t VQ, (H^Ml), (1^11)
Write your solution only on this side of the sheet!
D D D "1  sheet, .j 3  uco H H H E H Q,
points
r.    .n  r, ,n
'j   l*      'j   l' 'j
Encode the following posting:
• Countrymen: 687,1599,1978
using the variable byte code [2 points], and the gamma code (7), where 7(71) = (a(length of offset(n)), offset(n)) [2 points].
(m\ - {snt 128 + 32 + 8 + s +2 + 1 )2 * 10 1010 1111
(1539-68} = 312^= (S12+25"6+ 122 + 16^ = 11
(13^8-1593= 3=J3)2 =       t    +    +    + 8+ 2+1) = 1  01H 1011
0000  01O1   1*10  1111   oooo 0111 1001 0^ 0000 0010 tin 1011
5
111 111 1110  0 1010 1111      111 H11110, 1  1001 0000
11 111 1110, 0111 1011
Write your solution only on this side of the sheet!
sheet
H ,„H53EHD
,n   r,     ,1   r, ,-|
points
Compute the Levenshtein distance between Crypto and Corrupt using the matrix [2 points] and present at least one sequence of operations (insert, delete, replace, copy) that transform one term to the other [2 points].
		c	0			U	P	T
i		1	2	3		5"		1
c	-1	0	1	2	3		5	
	2	1	1	1	Z	3	H	
y	3	2	1	2	1	3	1	r
r	H	3	3	3	I	3	3	H
T	5"	4	H	H	H	H	H	3
o 1	G	5"	H	S	S	5	S	13
		c	R.	Y	P	T	0	
£		1	2	3	H	5"		
c	1	0	1	2	3	H	S	
0	2	1	1	Z	3		H	
		2		2	3	H	S	
		3	2	2.	3	H	S	
V	5"	<l	3	3	3	H	5	
		5	H	H	3	1	S	
T			5"	S	H	3	0	
0P£K .		our
copy	C	C
		*
K£Pl	y	0
	p	*
IMS	*	
IMS	*	K
(N5	*	0
IvJS		?
copy	T	T
	0	1 *
copy	c	C
		0
U?l	y	
K€TL	r	
*.€PL	i T	
IMS		p
	0	r
Write your solution only on this side of the sheet!
sheet
5  ,„ HE5EHD
points
Construct a permuterm index for the terms Pinyin, and Baybayin. [2 points]
?imyim|
FlNYllSl
IftyBfv/itf
AyBftyiN|&
3AyiNi$BBy AyiN^&AYS yiM^bfty^Pi
41 Bpty^ftyiM
Consider a search engine that indexes a total of 1,000,000,000 pages, each page containing 250 tokens
on average. Assume the parameters k = 30 and b = 0.5 for your computation.
What is the size of the vocabulary of the indexed collection as predicted by Heaps' law? [2 points]
b
M * 30• (iso- \ wo ooo ooo)111 =30- ( s2 ■ lo10) = zo-s■ \os = AS ooo boo
VoovbiAUruj   s'Mt :   15" 000 OOO terms
Write your solution only on this side of the sheet!