结构化网络中聚合Top-K查询优化技术  

Top-K Query for Aggregate Value in Structured Networks

作　　者：李柰[1] 王斌[1] 关晶[1] 王国仁[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《小型微型计算机系统》2007年第11期2033-2037,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(6057308960503036)资助;霍英东基金优选课题项目(104027)资助.

摘　　要：top-k查询在分布式环境中引起越来越多的关注,但是现存的一些top-k算法大都只适用于集中式网络.提出了一个解决分布式网络中top-k查询的新方法—Histogram-Container算法(简称为HC算法),它不仅网络延迟小,网络带宽花费少,而且能够运行在任何结构的分布式网络中.本文将基于一个树型拓扑网络来说明如何使用本地的直方图和bloom filter信息来优化查询,以及如何在中间节点进行部分结果的合并.实验评估和性能分析表明HC算法在网络带宽消耗和查询响应时间方面要优于其他同类方法.Top-k query processing has received more and more attention ,but existing top-k algorithms can be only applied in the centralized network. This paper presents a new algorithm to answer top-k query, called Histogram-Container （HC for short）, which can achieve major performance gains in terms of query response time and network bandwidth, and furthermore, it can resolve queries in any kind of structured overlay networks. We will show how to use local histogram and bloomfilter in a tree structure for optimizing the query and how to process intermediate results in inner peers. Our experimental results show that HC can achieve major performance gains in terms of network bandwidth, query response time.

关 键 词：TOP-K查询 直方图 BLOOM filter 分布式网络 

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