###
DOI:
Journal of Software:2009.20(9):2426-2435

基于R-Tree的高效异常轨迹检测算法
刘良旭,乔少杰,刘宾,乐嘉锦,唐常杰
(宁波工程学院 电子与信息工程学院,浙江 宁波 315016;东华大学 计算机科学与技术学院,上海 200051;西南交通大学 信息科学与技术学院,四川 成都 61003;四川大学 计算机学院,四川 成都 610065;Department of Computer Science, School of Computing, National University of Singapore, 117590, Singapore)
Efficient Trajectory Outlier Detection Algorithm Based on R-Tree
LIU Liang-Xu,QIAO Shao-Jie,LIU Bin,LE Jia-Jin,TANG Chang-Jie
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3832   Download 4650
Received:August 13, 2008    Revised:January 15, 2009
> 中文摘要: 提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1) 为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2) 针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义.
Abstract:Recent progress on location aware services, GPS and wireless technologies has made it possible to real-timely track moving object and collect a large quarlity of trajectories data. As a result, how to effectively discover the knowledge from these trajectory data becomes an attractive and interesting research topic. The new trajectory outlier detection, proposed in this paper, can be used to determine whether two trajectories are globally matched by calculating the local matching degree between every base comparing unit pairs. Firstly, this paper proposes a new distance measure approach, which treats k consecutive points as a local comparing unit to depict the local features in terms of trajectories, via calculating the matching degree between trajectory segments. In addition, the critical concepts as local match, global match and trajectory outlier are presented. Secondly, based on this distance measure method, a new trajectory outlier detection algorithm based on R-tree is proposed to improve the efficiency of outlier detection. The main idea behind this algorithm is to eliminate unnecessary distance computation by R-tree and distance characteristic matrix between every trajectory pair. Extensive experiments demonstrate the efficiency and effectiveness of the proposed algorithm for trajectory outlier detection.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60773169, 60473071 (国家自然科学基金); the 11th Five-Years Key Programs for Sci. &Tech. Development of China under Grant No.2006BAI05A01 (“十一五”国家科技支撑计划); the Youth Software Innovation Project of Sichuan Province of China under Grant No.2007AA0032 (四川省青年软件创新工程) Supported by the National Natural Science Foundation of China under Grant Nos.60773169, 60473071 (国家自然科学基金); the 11th Five-Years Key Programs for Sci. &Tech. Development of China under Grant No.2006BAI05A01 (“十一五”国家科技支撑计划); the Youth Software Innovation Project of Sichuan Province of China under Grant No.2007AA0032 (四川省青年软件创新工程)
Foundation items:
Reference text:

刘良旭,乔少杰,刘宾,乐嘉锦,唐常杰.基于R-Tree的高效异常轨迹检测算法.软件学报,2009,20(9):2426-2435

LIU Liang-Xu,QIAO Shao-Jie,LIU Bin,LE Jia-Jin,TANG Chang-Jie.Efficient Trajectory Outlier Detection Algorithm Based on R-Tree.Journal of Software,2009,20(9):2426-2435