作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (16): 17-20. doi: 10.3969/j.issn.1000-3428.2011.16.006

• 博士论文 • 上一篇    下一篇

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

王考杰 1,2,郑雪峰 1,宋一丁 2,曲阜平 3   

  1. (1. 北京科技大学信息工程学院,北京 100083;2. 总后勤部后勤科学研究所,北京 100071;3. 中国人民解放军65024部队,辽宁 大连 116041)
  • 收稿日期:2011-02-08 出版日期:2011-08-20 发布日期:2011-08-20
  • 作者简介:王考杰(1972-),男,博士,主研方向:数据流分析,数据挖掘;郑雪峰,教授;宋一丁、曲阜平,高级工程师、硕士
  • 基金资助:
    国家科技支撑计划基金资助重点项目(2006BAG01A07)

KNN Approximate Query for Trajectory Data Stream

WANG Kao-jie 1,2, ZHENG Xue-feng 1, SONG Yi-ding 2, QU Fu-ping 3   

  1. (1. School of Information Engineering, University of Science and Technology Beijing, Beijing 100083, China; 2. Logistics Scientific Institute, General Logistics Department, Beijing 100071, China; 3. PLA 65024 Unit, Dalian 116041, China)
  • Received:2011-02-08 Online:2011-08-20 Published:2011-08-20

摘要: 提出一种基于滑动窗口的K-最近邻(KNN)近似查询算法。将滑动窗口内数据通过聚类划分成若干大小不一的基本窗口,针对每个基本窗口给定一个采样率,对窗口内数据进行偏倚采样,形成数据流摘要,并基于该摘要,采用计算几何平面扫描算法执行分布式最近邻查询。仿真实验结果表明该算法有效,且具有较好的可扩展性。

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

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

Key words: trajectory data stream, local clustering, biased sampling, data synopses, K-Nearest Neighbor(KNN) query

中图分类号: