All

Question 1

DER algorithm

Answer 1

Step 1: replication
Step 2: local inner join
Step 3: select ROW ID of left table with no matches
Step 4: redistribute the ROW ID
Step 5: Store ROW ID that appears as many times as the number of processors
Step 6: Join

Question 2

ROJA Algorithm

Answer 2

Step 1: reshuffle the data based on the join attribute
Step 2: each processor performs the local outer join

Question 3

DOJA Algorithm

Answer 3

step 1: replication. we duplicate small table

step 2: local inner join

step 3: hash redistribute the inner join result based on attribute X

step 4: local outer join

Question 4

OJSO

Answer 4

When joining 3 tables:
1. Do redistribution on join attribute (same as ROJA)
2. local join (same as ROJA)
3. redistribute joined table & third table based on the join attribute
(ignore dangling records)
4. local join

Question 5

local join: scan cost
(after divide & broadcast)
(Optimizing main memory)

Answer 5

((R_i/P)+(S_i/P)-(M/P)) * IO

M = size of memory

Question 6

Speed up

Answer 6

concerned with processing speed while the same workload

elapsed time on uniprocessor / elapsed time on multiprocessor

Question 7

Scale up

Answer 7

concerned with increasing workload while maintaining processing speed

time on small system / time on large system

Question 8

Downside of a shared-nothing architecture

Answer 8

load balancing becomes difficult

Question 9

Downside of Shared-Memory & Shared-Disk architectures

Answer 9

suffers from memory and bus contention

Question 10

Process activation or involvement of parallel search algorithms

Answer 10

Question 10

Process activation or involvement of parallel search algorithms

Answer 10

Question 11

Key comparison of parallel search algorithms

Answer 11

Question 12

Divide and Broadcast […] join: Transfer cost

Answer 12

(S_i/P) x (n-1) x(m_p+m_l)

Question 13

Divide and Broadcast […] join: Receiving cost

Answer 13

(S/P - S_i/P) x (m_p)

Question 14

Divide and Broadcast […] join: Scan cost

Answer 14

(S_i/P) x IO

Question 15

Divide and Broadcast […] join: Select cost

Answer 15

|S_i| x (t_r + t_w)

Question 16

Divide and Broadcast […] join: Disk storing cost

Answer 16

(S/P - S_i/P) x IO

Question 17

Local join: Scan cost
(after divide & broadcast)

Answer 17

((R_i/P) + (S/P)) x IO

Question 18

Local Join: Select cost
(after divide & broadcast)

Answer 18

(|R_i| +|S|) x (tr + tw)

Question 19

Local Join: Join cost
(after divide & broadcast)

Answer 19

(|R_i| x (t_r + t_h) + (|S| x(t_r + t_h + t_j))

Question 20

Local join: Generating result cost
(after divide & broadcast)

Answer 20

|R_i| x \sigmaj x |S| x t_w

Question 21

Redistribution Step: select cost

Answer 21

(|Ri| + |Si|) (tr + tw)

Question 22

Redistribution step: finding destination cost

Answer 22

(|Ri| + |Si|) (td)

Question 23

Parallel Merge-All Sort

Answer 23

Question 24

Parallel Binary-Merge Sort

Answer 24

Question 25

Parallel Redistribution Binary-Merge Sort

Answer 25

Question 26

Parallel Redistribution Merge-All Sort

Answer 26

Question 27

Parallel Partitioned Sort

Answer 27

Question 28

Parallel Group-By

Answer 28

Question 29

DT: data parallelism

Answer 29

Data is partitioned vertically

Locally

1. each processor calculates entropy for its features

Globally

1. each processor shares entropy and target class count
2. determine the best splitting attribute
3. share which records to include in the subsequent partitions

iterative process: repeat the steps above

Question 30

DT: result parallelism

Answer 30

1. data is partitioned horizontally
2. each processor needs to exchange counts with other processors
3. determine the best splitting attribute for the root node
4. redistribute records by attribute to the processor assigned to this attribute
5. each processor shares entropy and information gain values
6. determine 2. splitting attribute
7. …

Question 31

Formula: Entropy

Answer 31

Question 32

ID3 algorithm

Answer 32

1. compute entropy for dataset
2. for every attribute/feature:
   
   1. calculate entropy for all categorical values
   2. take average information entropy for the current attributeS
   3. calculate the gain for the current attribute
3. pick the highest gain attribute
4. repeat until the tree is complete

Question 33

k-means: data parallelism

Answer 33

Initialization:

1. Divide the dataset among processors
2. Replicate the initial centroids to each processor

In each processor:

1. Compute the distance of each local data point to the centroids
2. Construct local clusters
3. Maintain a sum and a count of each local cluster
4. At each iteration, the master process computes the new means and sends them to all processors
5. Repeat steps 1-4 until convergence

Question 34

k-means: result parallelism

Answer 34

Initialization

1. Divide dataset D among P processors, and
   sort the data within each processor
2. Divide the initial centroids among processors
3. Allocate data points to the nearest cluster centroid

In each processor:

1. For each cluster, calculate the distance between each local data point and the cluster centroid
2. For extreme low and high data points in each cluster:
   
   1. If they are closer to centroid of other cluster of the same processor, then move these data points into
      the new cluster
   2. If they are closer to centroid of other cluster of different processor, then move these data points into
      a new processor
3. Repeat steps 1 & 2 until convergence

Question 35

Formula: Similarity

Answer 35

Question 36

Bounded data stream

Answer 36

The bounded stream will have a defined start and an end. […] we can ingest the entire data set before starting any computation

Question 37

Dense Vector –> Sparse Vector

Answer 37

Question 38

What is the purpose of watermarking?

Answer 38

to handle events that arrive late to the application
(e.g. event time =/= received time)