分布式数据的反Skyline查询算法  

Reverse Skyline Computation over Distributed Data

作　　者：杨萍萍[1] 赵雷[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《小型微型计算机系统》2014年第2期255-260,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61073061)资助

摘　　要：Skyline查询是一个典型的多准则优化问题,在多标准决策,数据挖掘以及市场分析等实际应用中起着越来越重要的作用.反skyline查询则是在skyline查询基础上提出的,它的查询结果与skyline查询相反,是返回以查询点作为其动态skyline点的数据集合.但此前的工作仅限于集中式数据上的反skyline查询.在现实应用中,基于更新成本、性能等考虑,数据经常是分散存放并通过网络互联的.诸如网上购物,环境监测等具体应用中,集中式算法不再适用于分布式环境.本文提出分支界限(BBDRS)和预排序(PDRS)两种分布式算法,尽可能的过滤掉远程站点上不可能成为反skyline点的数据,减少了发往协调站点的通信负载,降低协调站点计算量,以降低查询延迟.理论论证和实验数据都显示了该方法的可行性和有效性.Skyline query, as a typical problem about multi-criteria optimization, plays an important role in multi-criteria decision mak- ing, data mining and so on. Reverse skyline query is proposed based on skyline, in contract with skyline query, it returns the points treating the query point as their dynamic skyline points. However, till now, most of the work focuses on the centralized data and there is almost no work over distributed data. In practice,most of the data is stored over different sites connected by network in consideration of the cost and performance. As in on-line shopping and environment monitoring applications, traditional method for centralized data can＇t adapt to distributed data. In this paper,we propose a Branch and Bound-based Distributed Reverse Skyline（ BBDRS ） algorithm and a Presort-based Distributed Reverse Skyline （ PDRS ） algorithm to filter the data that cant be the results in distributed sites to re- duce overall communication load and system delay. Theoretical arguments and experimental data both show the correctness and effi- ciency of BBDRS and PDRS.

关 键 词：REVERSE SKYLINE 分布式 DYNAMIC SKYLINE SKYLINE 数据库查询 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]