# Fast Performance Modeling across Different Database Versions Using Partitioned Co-Kriging
## 4 Partitioned Co-Kriging Based Performance Prediction
### Performance Prediction with Partitioned Co-Kriging  
Using the above-mentioned prediction process, we now discuss the PCK method in Algorithm 1. **Random sampling. ** We collect training data in target domain by running a subject database with updated version on various configurations and record the resulting performance values. The selected configurations are generated by random sampling (RS) strategy, as it can effectively search for a large configuration space, especially when configuration parameters are not equally important [37] (line 1). **Clustering**. The partition of configuration space is achieved by clustering the adequate source samples (line 2). We use a well-studied technique, called k-means [38], to cluster the source samples into meaningful groups. The goal of the k-means algorithm is to divide \(M\) points in \(N\) dimensions into \(K\) clusters so that the within-cluster sum of squares is minimized. \(M\) is the number of the source samples. \(N\) equals to the number of configuration  
Figure 3: Overview of partitioned co-kriging approach. parameters add one; it means that we consider not only each configuration parameter, but also its performance value in clustering. This is because we aim to identify the different smooth regions. \(K\) clusters correspond to \(K\) different regions. ```
0:\(A\): the subject database; \(W\): workload; \(P\): configuration parameters; \(CB\): configuration bounds; \(S_{S}\): the available samples in source domain; \(K\): the number of clusters; \(VM\): variogram model; \(C_{U}\): the unseen configurations in target domain. 0:\(P_{U}\): performance predictions of the unseen configurations in target domain. 1:\(S_{T}\gets RS(N_{T},A,W,P,CB)\);
2:\(K\)-clustered \(S_{S}\gets k-means(S_{S},K)\);
3:\(K\)-clustered \(S_{T}\gets partition(S_{T},K\)-clustered \(S_{S})\);
4:\(K\)-clustered \(C_{U}\gets partition(C_{U},K\)-clustered \(S_{S})\);
5:for each \(c_{i}\in C_{U}\)do
6:\(p_{i}\gets co-kriging(S_{S},S_{T},c_{i},VM)\) in corresponding cluster;
7:endfor
8:return\(P_{U}\);
```  
**Algorithm 1**\(PCK(A,W,P,CB,S_{S},K,VM,C_{U})\). One of the drawbacks of using k-means is that we have to specify the number of clusters (\(K\)) before starting. On the one hand, the accuracy of prediction models can be increased by clustering different smooth regions. On the other hand, \(K\) should not be selected too large because of the small sample in target. Otherwise, the sample size in each region will be too small to learn a reliable prediction model. In conclusion, choosing \(K\) is a trade-off, and we are going to explore this problem in our experiments. **Partition**. After the clustering is complete, we get \(K\) smooth regions in configuration space. Then, \(K\) performance prediction models can be constructed using co-kriging. The input of co-kriging includes not only the source samples in the cluster, but also the target samples in corresponding region. In target domain, the region of a sample is determined by the Euclidean distances with source samples. In order to facilitate the co-kriging-based performance prediction in next step, the samples in both source and target are partitioned using the clustering results (line 3-4). **Co-kriging**. Kriging, a regression method, is a minimum variance unbiased linear estimator and has received wide use for ore reserve estimation applications in mining [20]. Kriging utilizes the spatial correlation, of the variable of interest with itself, to determine the weights in an optimal manner. Co-kriging is the logical extension of ordinary kriging to situations where two or more variables are spatially interdependent and the one whose values are to be estimated is not sampled as intensively as the others with which it is correlated [19]. Its advantage is that when the primary variable is difficult or expensive to obtain, the co-kriging method adopts the auxiliary variable that is easier to obtain and is correlated with the primary variable to predict the primary variable, thus improving the prediction accuracy (line 6).