不确定数据上两种查询的分布式聚集算法

被引：11

作者：

周逊

李建中

石胜飞

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

来源：

计算机研究与发展 | 2010年 / 47卷 / 05期

基金：

国家自然科学基金重点项目;

关键词：

不确定数据; 分布式聚集; Top-k查询; 过滤策略; 传感器网络;

D O I：

暂无

中图分类号：

TP212.9 [传感器的应用]; TN929.5 [移动通信];

学科分类号：

080202 ; 080402 ; 080904 ; 0810 ; 081001 ;

摘要：

不确定数据查询技术在军事、金融、电信等领域中起到了越来越重要的作用.不确定性数据在传感器网络、分布式Web Server及P2P系统等分布式系统中广泛存在.从这些系统中收集所有数据进行集中式查询将带来巨大的通信开销、时间延迟和存储代价.同时,由于不确定数据的特点,大多数集中式不确定查询算法在分布式环境下并不适用.给出不确定数据的最大值和Top-k聚集查询定义,并分别提出了基于过滤策略的分布式聚集算法.算法根据给出的3个过滤策略,利用数据的分布区间和概率进行筛选概率上限的计算,尽可能将不影响查询结果的数据抛弃.同时,算法以相对较小的代价归并保存并传输了计算最终查询结果所需要的"不可丢弃"数据.实验结果表明,在各类系统和数据条件下,过滤算法都能够正确地得到查询结果并显著降低系统的数据通信开销.

引用

页码：762 / 771

页数：10

共 3 条

[1] 不确定性数据管理技术研究综述 [J].

周傲英 ;

金澈清 ;

王国仁 ;

李建中 .

计算机学报, 2009, 32 (01) :1-16

[2]

On the representation and querying of sets of possible worlds[J] . Serge Abiteboul,Paris Kanellakis,Gosta Grahne.ACM SIGMOD Record . 1987 (3)

[3]

Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases .2 George Beskales,Mohamed A Soliman,Ihab F. Ilyas. Proceedings of the 34th International Conference on Very Large Data Bases, VLDB 2008 . 2008

← 1 →