HPPQ: A Parallel Package Queries Processing Approach for Large-Scale Data

Figure 3 illustrates the HS execution procedure, which is based on improved partial opposition-based learning to obtain the optimal solution of the centroid. The dashed box indicates the generate new candidate harmony phase. Unlike the basic HS, an improved partial opposition solution is constructed based on the current best harmony, which accelerates the convergence of the algorithm.

10.26599/BDMA.2018.9020014.F003 Fig. 3Harmony search based on improved partial opposition-based learning.

The framework of our method is shown in Algorithm 1.

Using an HS based on the improved partial opposition-based learning algorithm, the optimal solution based on the centroids of the sub-regions was obtained. But this was not the eventual solution to the package query. Therefore, it was necessary to replace the centroids of the sub-regions with the real data objects in the corresponding sub-regions to get the final solution.

Each sub-region where the centroid needs to be replaced is called a group. The set of groups, based on the improved partial opposition-based learning algorithm for HS is recorded as $G=\{g_1,g_2,\mathrm{\dots },g_{|G|}\}$ . The number of nodes in the cluster is $|N|$ and there evidently is $|G|\ge |N|$ . Therefore, the $|G|$ groups need to be assigned to the $|N|$ nodes in the cluster. The allocation algorithm is based on the number of combinations generated in each group, i.e., $\left(\begin{array}{c}|g_i|\\ |x_{|g_i|}^{best}|\end{array}\right)$ .

That is, the number of combinations of $|x_{|g_i|}^{best}|$ data objects is selected from the set of $|g_i|$ data objects so that, to achieve load balancing, the calculation load of each node is approximately the same.

The specific process of the group allocation algorithm is shown in Algorithm 2. The major steps are as follows.

First, eliminate sub-regions that do not require a replacement operation. That is, the centroids of these sub-regions have an element value of zero. All sub-regions with centroids that need to be replaced are composed of a set of groups and form a collection of nodes. The maximum number of combinations for each group to be replaced is calculated and arranged in descending order (line 1). The first few regions with the largest number of combinations are allocated to the nodes in the cluster in turn. Then, each time an unassigned group has the current maximum number of combinations, it is assigned to the node with the least calculation load (lines 2-7).

Figure 4 shows an example of how to allocate groups. Assume the optimal solution (2, 2, 2, 0, 0, 1, 1, 2) is obtained by using the partitioning results shown in Fig. 1 and the HS based on the improved partial opposition-based learning algorithm. There are four nodes in the cluster. If the value of the components corresponding to the centroid of the sub-region is zero, the data objects in that sub-region will not appear in the result set, so no replacement operations are required. The remaining six groups are sorted in descending order of combinations and we get the descending sequence group1, group2, group3, group6, group4, group5. First, the first four groups are assigned to each node in turn. Next, assign group4. At this point, the node with the least number of combinations in the cluster is $n_4$ , so assign group4 to $n_4$ . Similarly, assign group5 to $n_4$ .

10.26599/BDMA.2018.9020014.F004 Fig. 4The allocation process of groups.

Inferior replacement programs for sub-problems have less likelihood of appearing in the global optimal solution, and better replacement programs have a greater likelihood of appearing in the global optimal solution. Thus, some better replacement programs can be obtained by heuristic methods and any inferior replacement programs can be eliminated directly. Although this method reduces accuracy to a certain extent, it can significantly reduce the number of replacement programs that need to be adjusted, thereby reducing the run time required for the query. By using only some of the better replacement programs to consider the interaction between replacement programs in sub-problems, the run time required for the query is further reduced.

The parallel scheme can be used to generate the optimal harmony memory for each group. However, the replacement program for each group will affect the replacement programs of the remaining groups. Therefore, before presenting the parallel processing algorithm, we first introduce a number of metrics that are used in the algorithm to coordinate the replacement programs for each group.

(1) Relative change in total value:

(7) $$△v_{ij}=v_{ij}-v_{i{j}_{now}}$$

In Eq. ( 7 ), $v_{ij}$ represents the objective function value of the j-th replacement program in the i-th group. $v_{ijnow}$ represents the objective function value of the $j_{now}$ -th replacement program in the i-th group. $△v_{ij}$ represents the relative change in the objective function when the replacement program of the i-th group changes from $v_{ijnow}$ to $v_{ij}$ .

(2) Relative change in resource consumption:

(8) $$△c_{ij}=\underset{k}{\sum }\{c_{ijk}-c_{i{j}_{now}k}\cdot r_k/|\stackrel{\to }{r}|\}$$

In Eq. ( 8 ), $c_{ijk}$ represents the k-th resource consumption of the j-th replacement program in the i-th group, $c_{i{j}_{now}k}$ represents the k-th resource consumption of the $j_{now}$ -th replacement program in the i-th group. $r_k$ represents the current consumption of the k-th resource. $|\stackrel{\to }{r}|$ represents the current consumption of all resources.

(3) Scaled change of resource consumption for repairing unfeasible solutions:

(9) $$△c_{ij}^{over}=\underset{k}{\sum }\frac{c_{ijk}-c_{i{j}_{now}k}}{r_k-C_k}$$

In Eq. ( 9 ), $r_k-C_k$ represents the portion of the original replacement program that is exceeded on the k-th resource constraint.

(4) Scaled change of resource consumption for optimizing feasible solutions:

(10) $$△c_{ij}^{in}=\underset{k}{\sum }\frac{c_{ijk}-c_{i{j}_{now}k}}{C_k-r_k}$$

(5) Proportionality coefficient for repairing unfeasible solutions:

(11) $$u_{ij}^{over}=△c_{ij}^{over}/△v_{ij}$$

(6) Proportionality coefficient for optimized feasible solutions:

(12) $$u_{ij}^{in}=△c_{ij}^{in}/△v_{ij}$$

(7) Unfeasible coefficient:

(13) $$f_{ijk}=r_{ijk}/C_k$$

In Eq. ( 13 ), if there is always $f_{ijk}<1$ for all resource constraints, the current solution is feasible.

A parallel algorithm is proposed to efficiently replace the centroids of the sub-regions with the real data objects in the corresponding sub-region. The main premise of this is as follows: each node uses an HS based on the improved partial opposition-based learning algorithm to search the optimal harmony memory of each group in parallel. The candidate solutions in the harmony memory are sorted in descending order of value. Therefore, the solution with the highest value in each group is in first place. The solution of the first row of each group is taken as the initial solution based on the greedy strategy. Then, the solution is upgraded or downgraded based on different metrics to find the optimal solution that satisfies the constraints.

The framework of our algorithm is shown in Algorithm 3. The major steps of the parallel processing algorithm are as follows.

Step 1. Greedily form the initial solution (lines 3-7). The solution in the first place of each group is taken as the initial solution. If the initial solution is feasible, the optimal result set is obtained and returned. Otherwise, Step 2 is executed.

Step 2. Calculate the metrics in parallel and reduce the value of the candidate solution to get a feasible solution (lines 8-17). Calculate $u_{ij}^{over}$ of the replacement programs in each group, which has less value than the current replacement program in each group. Select the replacement program which is less valuable than the current replacement program in each group but has the largest global $u_{ij}^{over}$ . Replace the current replacement program in the corresponding group with the program which has the largest global $u_{ij}^{over}$ . If the modified solution is feasible, Step 3 is executed. Otherwise, Step 2 is executed.

Step 3. Get a better solution than the current solution (lines 19-28). For each replacement program that has more value than the current replacement program, the relative change in total resource consumption $△c_{ij}$ can not be negative. This means that there is no replacement program that has a greater value and consumes less total resources than the current replacement program. Therefore, we want to improve the value of the current replacement program if it ensures that the new solution obtained by the replacement operation is still feasible. If changing the current replacement program to a more valuable replacement program can make all the unfeasible coefficients for the resources still be $f_k\le 1$ , calculate its $u_{ij}^{in}$ . Select the replacement program which has the lowest global $u_{ij}^{in}$ . Replace the current replacement program in the corresponding group with the program which has the lowest global $u_{ij}^{in}$ . If there is a more valuable replacement program and it does not make the feasible solution become unfeasible, Step 3 is executed. Otherwise, stop the operation and return the current optimal solution.