关键词: 局部离群因子, [k]近邻, 距离矩阵, 网格, 记忆性, 邻域查询

Abstract: In view of the density based Local Outlier Factor（LOF） algorithm, it is necessary to calculate the distance matrix for the [k] nearest neighbor search, but the time complexity of this algorithm is high, and it is not suitable for the large-scale data set detection. The local outlier detection algorithm based on the grid query（LOGD） is proposed. This algorithm uses the characteristic that the nearest [k] data points from the data points in the target grid, which must be memorable in the target grid or the nearest adjacent grid of the target grid, to improve the neighborhood query operation of the LOF algorithm, and reduce the distance calculation from the neighborhood query. Experimental results show that the algorithm has the same detection accuracy as the original LOF algorithm, and effectively reduces the time of outlier detection.

Key words: local outlier factor, [k]-nearest neighbors, distance matrix, grid, memory, neighborhood query