一种基于支配图的多维数据流Top-k高效查询算法-论文.pdf

《一种基于支配图的多维数据流Top-k高效查询算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第31卷第6期计算机应用研究Vo1．31No．62014年6月ApplicationResearchofComputersJun．2014一种基于支配图的多维数据流Top—k高效查询算法刘卉，曾利军，黄樱(湖南工学院计算机与信息科学学院，湖南衡阳421002)摘要：为改善传感器网络多维数据查询扩展、减少通信量及提高查询精度，提出了一种新的用户多维数据查询处理构架。该处理框架能有效实现支配图，并能根据用户偏好函数进行任意数据查询。该框架在节点通信量上提出了更新滤波器算法和节点处理抽取算法来达到减少数据通信量，在滤波器算法中利用滤波器来避免sink分发所有的数据的目的，

2、而节点处理算法则采用自适应分发数据机制来减少数据的通信量。仿真结果表明，改进数据查询算法比中央收集算法和基本查询算法在通信量上有明显的减少。与中央处理算法相比，通信量减少了80％以上。关键词：查询扩展；查询精度；偏好函数；滤波器；抽取算法中图分类号：TP393；TP'301．6文献标志码：A文章编号：1001—3695(2014)06-1791-04doi：10．3969／j．issn．1001—3695．2014．06．045High--eficiencyTop·-kqueriesalgorithmonmulti·-dimensionaldatastreamsba

3、sedondominationgraphLIUHui，ZENGLi-jun，HUANGYing(SchoolofComputer&InformationScience，HunanInstituteofTechnology，HengyangHunan421002，China)’Abstract：Toimprovethequeryexpansiononmulti—dimensionaldatainsensornetworks，reducecommunicationtrafficandimprovethequeryprecision，thispaperproposedan

4、ewframeworkofqueryprocessonusermulti—dimensionaldata．TheLame—workcouldeffectivelyrealizedominationgraph，whichimplementeddataqueryatrandomaccordingtouserpreferencefunc—tion．Theframeworkonnodecommunicationtrafficproposedupdatefilteralgorithmandnodeextractionalgorithminordertoreducedataco

5、mmunicationtraffic，itmadeuseofthefiltertoavoidsinkdeliveralltheRS。．^datatothefilteralgorithm，andthenodeextractionalgorithmusesdanadaptivedatadistributionmechanismtoreducedatacommunicationtraffic．Thesimula—tionresultsindicatethatthemodifieddataqueriesalgorithmisasharpfallofcommunication

6、trafficthanthecentralcollectionalgorithmandthebasicqueryalgorithm．Itcompareswiththecentralprocessingalgorithmoncommunicationtraffictoreduceby80％ormore．Keywords：queryexpansion；queryprecision；preferencefunction；filter；extractionalgorithm的精确度。Zeinalipont等人口’提出了利用阈值的Top．k数据0引言查询算法，通过设置各属性域

7、的阈值以此来减少向基站发送无用数据。Wu等人在传感器网络节点中设置多个滤波器以数据库查询应用领域中的Top—k查询，即从海量的数据库此来过滤无用数据。以上算法在查询效率和减少能耗上做了中提取K个数据点或数据集。在这些应用中主要面临两个方大量研究工作，提高了传感器网络的性能，但所研究的数据领面的挑战：a)从用户角度考虑，用户数量级较大且每个用户都域为一维数据集。有自己不同的需求，用户在查询不同时刻、不同维数的数据有传感器多维数据查询在理论和实际研究中同样具有重要着不同权重，因此需要提出与多用户请求相同数量的查询，这意义。例如在海洋数据检测研究中，海洋生物学家关注的