关键词: 最近邻查询, 分布式环境, 近似算法, 数据流

Abstract: 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.

Key words: nearest neighbors query, distributed environment, approximate algorithm, data stream