KNN-Based Approximate Outlier Detection Algorithm Over IoT Streaming Data

Zhu, Rui; Ji, Xiaoling; Yu, Danyang; Tan, Zhiyuan; Zhao, Liang; Li, Jiajia; Xia, Xiufeng

Abstract

KNN-Based outlier detection over IoT streaming data is a fundamental problem, which has many applications. However, due to its computational complexity, existing efforts cannot efficiently work in the IoT streaming data. In this paper, we propose a novel framework named GAAOD(Grid-based Approximate Average Outlier Detection) to support KNN-Based outlier detection over IoT streaming data. Firstly, GAAOD introduces a grid-based index to manage summary information of streaming data. It can self-adaptively adjust the resolution of cells, and achieve the goal of efficiently filtering objects that almost cannot become outliers. Secondly, GAAOD uses a min-heap-based algorithm to compute the distance upper-/lower-bound between objects and their k-th nearest neighbors respectively. Thirdly, GAAOD utilizes a k-skyband based algorithm to maintain outliers and candidate outliers. Theoretical analysis and experimental results verify the efficiency and accuracy of GAAOD. INDEX TERMS IoT streaming data, KNN-based outliers, indexes, error guarantee.

Citation

Zhu, R., Ji, X., Yu, D., Tan, Z., Zhao, L., Li, J., & Xia, X. (2020). KNN-Based Approximate Outlier Detection Algorithm Over IoT Streaming Data. IEEE Access, 8, 42749-42759. https://doi.org/10.1109/access.2020.2977114

• Journal Article Type: Article
• Acceptance Date: Feb 15, 2020
• Online Publication Date: Feb 28, 2020
• Publication Date: 2020
• Deposit Date: Mar 13, 2020
• Publicly Available Date: Mar 13, 2020
• Journal: IEEE Access
• Electronic ISSN: 2169-3536
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 8
• Pages: 42749-42759
• DOI: https://doi.org/10.1109/access.2020.2977114
• Keywords: Anomaly detection, Microsoft Windows, Indexes, Monitoring, Approximation algorithms, Sensors, Heuristic algorithms
• Public URL: http://researchrepository.napier.ac.uk/Output/2633023