一种网格化高并发Skyline查询处理方法

Cells Based Highly Parallel Skyline Query Processing Method

为减少冗余支配测试对Skyline查询性能的影响并提高Skyline查询处理的效率,本文将测试单位扩大为网格,并设计了一种基于网格分层划分的Skyline查询方法.通过不断缩小Skyline点集所在网格的方式,使网格之间的支配关系与点支配关系重合,从而避免了点与点之间大量无效的支配测试,提升了Skyline查询处理的效率.方法中同一层的网格可并行计算,且层次计算过程可达到任意精度,适用于计算能力有限但对结果精度要求不高的场合.实验结果表明,方法与现有Skyline查询处理方式相比具有数据吞吐量大、响应速度快等特点,在拥有高性能GPU或多核CPU等高并发环境下其优势更为明显.

In order to release the impact of redundant domination testing on querying efficiency of Skyline processing,and to improve the efficiency of Skyline query processing,we expand the domination testing target from points to grids.We also design a cell division-based Skyline query processing method.In this method,we incrementally shrink the cells that contain Skyline points where we can prove that the domination relationship between cells are the same as that between points.By this means,we avoid tremendous redundant domination testing between points and hence improve the efficiency.In our method,cells in the same layer can be processed in parallel.Moreover,the precision can be reached at any level.Therefore,our method is more suitable than existing method in cases that the processing ability is limited,and the precision requirement is not high.The experimental results show that,compared with existing methods,our method can handle more data and response more rapidly.The advantage is more obvious in when high-end GPU or multi-core CPU is available.