一种基于动态修正值的分布数据流Top-K查询处理算法  

A DYNAMIC ADJUSTMENT FACTOR BASED ALGORITHM FOR TOP-K QUERIES

作　　者：刘维弋[1] 金远平[1] 

机构地区：[1]东南大学计算机科学与工程学院,江苏南京210096

出　　处：《计算机应用与软件》2009年第1期53-56,共4页Computer Applications and Software

基　　金：国家自然科学基金重大研究资助项目(90412014);国家自然科学基金项目(60603040)

摘　　要：对分布式数据流进行查询,得到数值最大的K个对象(Top-K观测查询),最直接的解决方法是由中心结点处理分布式数据流,但这种方法导致中心结点和网络负载较大。提出一种基于动态修正值的查询算法,通过对观测数据进行计算得到修正值,并利用该修正值对不同结点处的对象数据进行操作,从而无需将结点数据流全部发送到中心结点就能完成Top-K观测查询。因而可以减少对网络带宽的要求和降低中心结点的负载,同时还能保持查询结果的完全准确。The K largest values can be obtained by querying the distributed data streams （ Top-K monitoring queries）. The straightforward method is to process the data streams on a coordinator. However,this leads to heavy loads on the coordinator and the network. A dynamic ad- justment factor based algorithm for Top-K monitoring queries is proposed. The overall communication cost and the load of the coordinator can be reduced significantly, and at the same time the preciseness of the query results is fully guaranteed.

关 键 词：分布式数据流 Top—K观测查询 网络负载 动态修正值 

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