分布式环境下的Skyline代表点查询

Skyline query of representative objects over distributed database

为了克服Skyline查询的不足即结果集大小无法控制,提出了Skyline代表点查询,返回k个可描述全局Skyline轮廓的Skyline代表点。研究了分布式环境下的Skyline代表点查询,提出了Naive算法和FDRA。Naive算法首先转移每个子节点上满足条件的两个局部代表点,再通过比较传来的局部代表点间的评价函数值大小决定子节点是否需要传送余下的局部点,以实现剪枝非代表点;与之相比,FDRA的改进在于过滤元组的选择,运用反馈方法,将每次动态更新最大评价函数值的点作为过滤元组,大大降低了计算代价,中心服务器每次只发送过滤元组到分布节点,这样可以尽早且最大限度地剪枝不可能成为代表的Skyline点。提出的算法降低了服务器间的通信开销,返回了正确的结果集,实验论证了算法的有效性与高效性。

In order to overcome the shortcoming of Skyline query that size of results could not be controlled, this paper pres- ented Skyline query of representative objects to return k Skyline representative objects which could describe the full Skyline contour. It studied the problem of representative Skyline query over distributed databases and introduced Naive algorithm and FDRA. To remove the non-representative Skyline points, Naive algorithm first transferd two local representatives which satis- fied conditions on each child nodes, and then decided whether transfer other local representatives according to the evaluation function values of the representatives. Compared to Naive algorithm, FDRA improved the choice of filter tuples, dynamically chose points with max evaluation value as filter tuples, reduced the computational cost with feedback method. The center serv- er only sent the filter tuples to other nodes to maximally remove the dominated points which would not become representative points as early as possible. The algorithm reduced the communication cost and returned the correct result, and experiments demonstrate the effectiveness and efficiency.