一种实时监控最近邻的近似算法  

An approximate approach to monitoring nearest neighbors in real time

作　　者：金澈清[1] 崇志宏[2] 周傲英[3] 

机构地区：[1]华东理工大学计算机科学与工程系,上海200237 [2]东南大学计算机科学与工程学院,南京211189 [3]复旦大学计算机科学与工程系,上海200433

出　　处：《计算机科学与探索》2007年第2期146-159,共14页Journal of Frontiers of Computer Science and Technology

基　　金：the Key Project of National Natural Science Foundation of China under Grant No.6049325;6049327(国家自然科学基金重大项目).

摘　　要：处理分布式环境下高速数据的最大挑战在于如何利用少量网络资源输出高质量的查询结果。对面向分布式环境的最近邻查询问题进行了研究,提出了一种基于过滤器的新方法,不仅能计算精确查询结果,还能够处理五类近似查询。该方法在各个远程站点均安装了智能过滤器,并通过合理设置过滤器的范围来降低数据传输量。理论分析及基于模拟数据集合和真实数据集合的实验报告均表明新方法具有较高的性能。The biggest challenge to processing high-speed data over distributed environment is to output qualified results by using small amount of network resource. The paper studies how to cope with nearest neighbors query over distributed environment and proposes a novel solution, which is capable of answering not only precise query, but also five kinds of approximate queries. After installing a Smart Filter in each remote site to filter parts of incoming data, the novel approach continuously adjusts the range monitored by each filter to reduce the overall communication cost. Theoretic analysis and experimental results based on synthetic datasets and real dataset indicate that new approach owns good performance.

关 键 词：实时监控 最近邻查询 近似算法 分布式环境 过滤器 数据集合 查询结果 新方法 网络资源 数据传输 实验报告 理论分析 近似查询 合理设置 高速数据 处理 远程站 智能 质量 性能 

分 类 号：TP[自动化与计算机技术]