使用网格索引的分布式数据流上K-Skyband连续查询算法  

Grid Index Based Continuous K-Skyband Query Algorithm over Distributed Data Streams

作　　者：詹彦溥 赵雷[1] 

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

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

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

摘　　要：K-Skyband查询是Skyline查询的扩展,能够返回那些自身具有潜在价值但被Skyline查询遗漏的点,在偏好搜索和多目标决策支持领域均有重要作用.此前关于K-Skyband查询的研究局限于集中式数据集,然而,分布式数据流上K-Skyband连续查询问题更有现实意义,它可以应用到诸如自然灾害预测和网络安全检测等方面.为了有效解决上述问题,提出了通过传送站点本地K-Skyband增量来减少站点间通信开销的算法GBIFA.此外,为了降低GBIFA算法的时间开销,采用规则的网格索引组织数据,并利用支配区域划分方法来避免更新维护时数据点间大量的支配测试.实验表明GBIFA算法在减少通信开销和查询时间上的有效性.K-Skyband query is an extension of Skyline query,it plays an important role in preference query and multi-criteria decision making because it can find those points which are potentially valuable but omitted by Skyline. Previous research on the K-Skyband query is limited to centralized data set, however, continuous K-Skyband monitoring over Distributed Data Streams has more practical significance, such as natural disasters prediction and network security monitoring. In order to solve the problem proposed effectively, a novel algorithm GBIFA based on delivering the incremental K-Skyband is developed to reduce the communication overhead between sites. Furthermore, a regular grid index is used to organize the data to accelerate the server processing time by taking advantage of dominating region partition which will contribute to avoiding dominating tests during update maintenance. Extensive experiments prove the validity of GBIFA.

关 键 词：分布式数据流 SKYLINE K-Skyband 连续查询 通信开销 

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