Database Systems: The Complete Book
▼ ❑ Chapter 22
▼ ❑ Section 1
▼ ❑ 1
• ❑ a 25%
• ❑ b 0%
▼ ❑ Section 2
• ❑ 1 F1 = {milk, coke, beer, pepsi, juice}
F2 = {milk, beer}, {milk, pepsi}, {beer, pepsi}
F3 = { }
▼ ❑ 2
▼ ❑ 5
• ❑ a (1/10)2(sb) + (1/1000)(sb) + (1/10000)(sb)
• ❑ b (1/1000)(sb) + (1/10000)(sb) + (1/10000000)(sb) + (1/1000000)(sb)
▼ ❑ 6
• ❑ a Map: Each processor counts all local items.
‘ def’
‘def ‘
‘ef g’
‘f gh’
‘ ghi’
▼ ❑ 3
• ❑ a {3, 3, 9}
▼ ❑ 4
• ❑ a {3, 6, 3}
• ❑ b {7, 5, 5}
• ❑ c {7, 5, 5}
▼ ❑ 5
• ❑ a Map: Compute minhash for each row.
Reduce: Process results locally.
• ❑ b Map: Each processor computer minhash-so-far. Do until all data has
been processed.
▼ ❑ Section 4
• ❑ a
• ❑ b
▼ ❑ Section 5
▼ ❑ 1
• ❑ a
• ❑ b
• ❑ 2 1. d(x,y) >= 0 for all x,y
summation of positive numbers are always postive
2. d(x,y) = 0 if x=y
if (x,y) = 0, then every xi – yi = 0 => xi = yi
• ❑ 4
Clusters: {AEBFC, D}
▼ ❑ 5
• ❑ a B, F, A
• ❑ b C, F, A