Accelerating Skycube Computation with Partial and Parallel Processing for Service Selection

Recently researchers use skyline techniques to optimize service selection procedure, where they can filter those low-quality web services from the large amount of candidates and return a much smaller high-quality service set. The skycube concept is adopted for quickly responding to the skyline queries with different combinations of Quality of Web Service (QoWS) parameters. As the skycube computation is quite time-consuming, it is a compelling challenge to accelerate this procedure. However, the current solutions usually have a number of redundant computations which will significantly affect the efficiency. To address such drawbacks, after an in-depth analysis of skycube computation procedure, we introduce a partial skycube, which only consists of the skylines with frequently used combinations of QoWS. Then the computational relationships between the skyline on one subspace and its parent-space are studied. Based on the relationships, we develop ${\sf {ParCube}}$ ParCube algorithm to speedup partial skycube computation by reusing the intermediate comparison results. Meanwhile, at the execution phase, ${\sf {ParCube}}$ ParCube can be further optimized with parallel execution mode and optimized scheduling strategy. Finally, we evaluate the efficiency and scalability of ${\sf {ParCube}}$ ParCube on both single machine and cluster environment. The results show that ${\sf {ParCube}}$ ParCube can efficiently compute partial skycube and scale well in cluster environment.