面向轨迹数据流的KNN近似查询  

KNN Approximate Query for Trajectory Data Stream

作　　者：王考杰[1,2] 郑雪峰[1] 宋一丁[2] 曲阜平[3] 

机构地区：[1]北京科技大学信息工程学院 [2]总后勤部后勤科学研究所 [3]中国人民解放军65024部队

出　　处：《计算机工程》2011年第16期17-20,共4页Computer Engineering

基　　金：国家科技支撑计划基金资助重点项目(2006BAG01A07)

摘　　要：提出一种基于滑动窗口的K-最近邻(KNN)近似查询算法。将滑动窗口内数据通过聚类划分成若干大小不一的基本窗口,针对每个基本窗口给定一个采样率,对窗口内数据进行偏倚采样,形成数据流摘要,并基于该摘要,采用计算几何平面扫描算法执行分布式最近邻查询。仿真实验结果表明该算法有效,且具有较好的可扩展性。This paper proposes a novel approach for continuous approximate query over trajectory stream based on sliding window.Through local clustering,the sliding window is divide into various sized basic windows and sampling the data elements of a basic window using biased sampling rate,forms trajectory stream synopses.Toward such synopses,it can implement distributed K-Nearest Neighbor（KNN） queries utilizing the plane sweep algorithm of computational geometry.The extensive experiments verify the effectiveness of proposed algorithm and it has better expansibility.

关 键 词：轨迹数据流 局部聚类 偏倚采样 数据摘要 K-最近邻查询 

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