基于R-Tree的高效异常轨迹检测算法

被引：65

作者：

刘良旭 ^{[1
,2
]}

乔少杰 ^{[3
,4
]}

刘宾 ^{[5
]}

乐嘉锦 ^{[2
]}

唐常杰 ^{[4
]}

机构：

[1] 宁波工程学院电子与信息工程学院

[2] 东华大学计算机科学与技术学院

[3] 西南交通大学信息科学与技术学院

[4] 四川大学计算机学院

[5] Department of Computer Science,School of Computing,National University of Singapore

来源：

软件学报 | 2009年 / 20卷 / 09期

关键词：

异常轨迹检测; R树; 基于平移的最小Hausdorff距离; 全局匹配; 局部匹配;

D O I：

暂无

中图分类号：

TP274.4 [];

学科分类号：

摘要：

提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1)为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2)针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义.

引用

页码：2426 / 2435

页数：10

共 3 条

[1]

Distance-Based Outliers: Algorithms and Applications.[J] Edwin M. Knorr;Raymond T. Ng;Vladimir Tucakov VLDB J. 2000,

[2]

The upper envelope of voronoi surfaces and its applications[J] Daniel P. Huttenlocher;Klara Kedem;Micha Sharir Discrete & Computational Geometry 1993,

[3]

LOF:Identifying density-based local outliers Breunig MM;Kriegel HP;Ng RT;Sander J; Proc.of the SIGMOD2000 2000,

← 1 →