Description
Q1. (40 marks)
Consider the following base cuboid Sales with four tuples and the aggregate function
SUM:
Location, Time, and Item are dimensions and Quantity is the measure. Suppose the system has builtin support for the value ALL.
 (1) List the tuples in the complete data cube of R in a tabular form with 4 attributes, i.e., Location, T ime, Item, SUM(Quantity)?
 (2) Write down an equivalent SQL statement that computes the same result (i.e., the cube). You can only use standard SQL constructs, i.e., no CUBE BY clause.
 (3) Consider the following iceberg cube query:
SELECT Location, Time, Item, SUM(Quantity)
FROM Sales CUBE BY Location, Time, Item HAVING COUNT(*) > 1
Draw the result of the query in a tabular form.
(4) Assume that we adopt a MOLAP architecture to store the full data cube of R, with
the following mapping functions:
1 if x = ‘Sydney’,
2 if x = ‘Melbourne’, 0 ifx=ALL.
1 if x = 2005,
Location 
T ime 
I tem 
Quantity 
Sydney Sydney Sydney Melbourne 
2005 2006 2006 2005 
PS2 PS2 Wii XBox 360 
1400 1500 500 1700 
fLocation(x) =
fTime(x) = 2 if x = 2006,
0 ifx=ALL. 1
2
DUE ON 20:59 12 APR, 2020 (SUN)
1 if x = ‘PS2’,
2 if x = ‘XBox 360’, 3 if x = ‘Wii’,
0 ifx=ALL.
Draw the MOLAP cube (i.e., sparse multidimensional array) in a tabular form of (ArrayIndex,Value). You also need to write down the function you chose to map a multidimensional point to a onedimensioinal point.
Q2. (30 marks)
fItem(x) =
Consider the given similarity matrix. You are asked to perform group average hierar chical clustering on this dataset.
You need to show the steps and final result of the clustering algorithm. You will show the final results by drawing a dendrogram. The dendrogram should clearly show the order in which the points are merged.
p1 
p2 
p3 
p4 
p5 

p1 p2 p3 p4 p5 
1.00 0.10 0.41 0.55 0.35 
0.10 1.00 0.64 0.47 0.98 
0.41 0.64 1.00 0.44 0.85 
0.55 0.47 0.44 1.00 0.76 
0.35 0.98 0.85 0.76 1.00 
Q3. (30 marks)
1 2 3 4 5 6 7
8 9
10
Data: D is a dataset of n ddimensional points; k is the number of clusters. Initialize k centers C = [c1, c2, . . . , ck];
canStop ← false;
while canStop = false do
Initialize k empty clusters G = [g1, g2, . . . , gk]; for each data point p ∈ D do
cx ← NearestCenter(p, C); gcx .append(p);
for each group g ∈ G do
ci ← ComputeCenter(g);
return G;
Algorithm 1: kmeans(D, k)
Consider the (slightly incomplete) kmeans clustering algorithm as depicted in Algo rithm 1.
COMP9318 (20T1) ASSIGNMENT 1 3
(1) Assume that the stopping criterion is till the algorithm converges to the final k clusters. Can you insert several lines of pseudocode to the algorithm to implement this logic? You are not allowed to change the first 7 lines though.
(2) The cost of k clusters is just the total cost of each group gi, or formally k
cost(g1, g2, . . . , gk) = cost(gi) i=1
cost(gi) is the sum of squared distances of all its constituent points to the center ci, or
cost(gi) = dist2(p, ci) p∈gi
dist() is the Euclidean distance. Now show that the cost of k clusters as evaluated at the end of each iteration (i.e., after Line 9 in the current algorithm) never increases. (You may assume d = 2)
(3) Prove that the cost of clusters obtained by kmeans algorithm always converges to a local minima. You can make use of the previous conclusion even if you have not proved it.
Submission
Please write down your answers in a file named ass1.pdf. You must write down your name and student ID on the first page. You should typeset your answers in LATEX or MS Word. We do not accept handwritten answers.
You can submit your file by
give cs9318 ass1 ass1.pdf
Hint 1. In fact, the two loops (Lines 5–7 and Lines 8–9) never increases the cost.