| 本文已被：浏览 6071次 下载 7461次 |
码上扫一扫！ |
|
|
| 有效预处理P2P 网络中的子空间skyline 查询 |
|
黄震华1,2, 王智慧3, 郭建魁3, 汪 卫3, 施伯乐3
|
|
1.同济大学 电子与信息工程学院,上海 201804;2.嵌入式系统与服务计算教育部重点实验室(同济大学),上海 200092;3.复旦大学 计算机与信息技术系,上海 200433
|
|
| 摘要: |
| 多维空间的skyline 查询处理是近年来数据库领域的一个研究重点和热点.Vlachou 等人首次考虑如何在P2P 网络中有效进行子空间上的skyline 查询,并提出“扩展skyline 集合”的概念来减少预处理时的网络传输量.然而实验评估表明,扩展skyline 集合只能有限地减少子空间skyline 查询预处理的数据传输量.基于此,提出一种缩减处理时数据传输量的有效方法TPAOSS(three-phase algorithm for optimizing skyline scalar).TPAOSS 算法根据全空间skyline 集合与子空间skyline 集合间的语义关系分3 个阶段来传输必要的数据,其中第1 阶段发送全空间skyline
对象;第2 阶段接收种子skyline 对象;而第3 阶段基于Bloom filter 技术发送种子skyline 对象在子空间上的重复对象.为了降低第2 阶段的数据传输量,给出两种接收种子skyline 对象的有效策略.理论分析和实验评估结果表明,所给出的算法具有有效性和实用性. |
| 关键词: 子空间skyline 查询 Bloom filter super-peer 体系结构 查询优化 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60303008 (国家自然科学基金); the National Basic Research Program of China under Grant No.2005CB321905 (国家重点基础研究发展计划(973)) |
|
| Efficient Preprocessing of Subspace Skyline Queries in P2P Networks |
|
|
| Abstract: |
| 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. |
| Key words: subspace skyline query Bloom filter super-peer architecture query optimization |
