结合非空间属性的通用Skyline查询处理技术

General Skyline Query Processing Technology Combining with Non-spatial Attributes

Skyline查询作为多目标决策的重要手段之一,近年来在各个领域得到广泛的应用。提出了结合非空间属性的通用Skyline查询处理技术,采用R树对设施集及数据集建立索引,并提出了两种方法来计算Skyline。第一种是基于全最近邻算法的扩展,通过计算静态Skyline结果来裁剪部分数据集。另一种是基于渐进最近邻的算法,采用查询点导向的搜索方法,利用静态Skyline结果计算与每一类设施最远的距离,将其作为边界阈值对数据点集进行裁剪,采用数据点导向的搜索方法,为裁剪后的每一个数据点计算距其最近的设施,并将数据点与设施的距离映射到多维距离空间中,结合非空间属性进行Skyline计算。实验结果表明,第二种方法减少了I/O次数,降低了CPU执行时间,提高了计算效率。

As one of the important methods for multi-criteria decision making problems, the Skyline query processing technologies have been widely studied in many applications. This paper proposes the general Skyline query processing technology combining with non-spatial attributes while R tree is adopted to index the facility set and the dataset. Two algorithms are provided to compute the Skyline results. The first algorithm is the extension of Skyline query algorithm based on all nearest neighbor method, which cuts off part of the dataset by computing the static Skyline results. The second algorithm is based on incremental nearest neighbor method, which utilizes the facility oriented searching method.The algorithm calculates the farthest distances between the static Skyline results and each type of facilities. The distances are set to bound thresholds so as to cut off data points which are farther than them. For the left points, data oriented search method is used to compute the nearest facilities of all types. After that, the distances between the data points and the facilities are mapped to the multi-dimensional distance space so as to compute the Skyline result combining with non-spatial attributes. The experimental results show that for the second algorithm the number of I/Os and CPU time are greatly reduced thus improves the computational efficiency.