有效预处理P2P网络中的子空间skyline查询  

Efficient Preprocessing of Subspace Skyline Queries in P2P Networks

作　　者：黄震华[1,2] 王智慧[3] 郭建魁[3] 汪卫[3] 施伯乐[3] 

机构地区：[1]同济大学电子与信息工程学院,上海201804 [2]嵌入式系统与服务计算教育部重点实验室(同济大学),上海200092 [3]复旦大学计算机与信息技术系,上海200433

出　　处：《软件学报》2009年第7期1825-1838,共14页Journal of Software

基　　金：国家自然科学基金No.60303008;国家重点基础研究发展计划(973)No.2005CB321905~~

摘　　要：多维空间的skyline查询处理是近年来数据库领域的一个研究重点和热点.Vlachou等人首次考虑如何在P2P网络中有效进行子空间上的skyline查询,并提出"扩展skyline集合"的概念来减少预处理时的网络传输量.然而实验评估表明,扩展skyline集合只能有限地减少子空间skyline查询预处理的数据传输量.基于此,提出一种缩减预处理时数据传输量的有效方法TPAOSS(three-phase algorithm for optimizing skyline scalar).TPAOSS算法根据全空间skyline集合与子空间skyline集合间的语义关系分3个阶段来传输必要的数据,其中第1阶段发送全空间skyline对象;第2阶段接收种子skyline对象;而第3阶段基于Bloomfilter技术发送种子skyline对象在子空间上的重复对象.为了降低第2阶段的数据传输量,给出两种接收种子skyline对象的有效策略.理论分析和实验评估结果表明,所给出的算法具有有效性和实用性.Skyline query processing has recently received a lot of attention in database community. Lately, Akrivi Vlachou and D. Christos considered how to efficiently process subspace skyline queries in peer-to-peer networks, and proposed the concept of ＂extended skyline set＂ to reduce the volume of data transferred in the preprocessing phase for the first time. However, the experimental evaluation shows that this data structure is extremely limited in reducing the volume of data transferred in the preprocessing phase, Motivated by these facts, this paper proposes an efficient algorithm, i.e. TPAOSS （three-phase algorithm for optimizing skyline scalar）, to reduce the volume of data transferred in the preprocessing phase. TPAOSS algorithm is based on the semantic relationship between full-space skylines and subspace skylines, and transfers the data through three phases. In the first phase, it only sends full-space skylines. In the second phase, it receives seed skylines. In the third phase, it exploits Bloom filter technology to obtain and send the replicated objects with seed skylines on the subspaces. Particularly, the paper presents two efficient strategies to reduce the volume of data transferred in the second phase. Furthermore, it presents detailed theoretical analyses and extensive experiments that demonstrate these algorithms are both efficient and effective.

关 键 词：子空间skyline查询 BLOOMFILTER super-peer体系结构 查询优化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]