Lune

VLDB2021Top-tier venue

Real-Time Distance-Based Outlier Detection in Data Streams

Luan V. Tran, Minyoung Mun, Cyrus Shahabi

Abstract

Real-time outlier detection in data streams has drawn much attention recently as many applications need to be able to detect abnormal behaviors as soon as they occur. The arrival and departure of streaming data on edge devices impose new challenges to process the data quickly in real-time due to memory and CPU limitations of these devices. Existing methods are slow and not memory efficient as they mostly focus on quick detection of inliers and pay less attention to expediting neighbor searches for outlier candidates. In this study, we propose a new algorithm, CPOD, to improve the efficiency of outlier detections while reducing its memory requirements. CPOD uses a unique data structure called "core point" with multi-distance indexing to both quickly identify inliers and reduce neighbor search spaces for outlier candidates. We show that with six real-world and one synthetic dataset, CPOD is, on average, 10, 19, and 73 times faster than M_MCOD, NETS, and MCOD, respectively, while consuming low memory.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. TranAD: Deep Transformer Networks for Anomaly Detection in Multivariate Time Series DataShreshth Tuli, Giuliano Casale, Nicholas R. JenningsVLDB 2022 · 930 citations
  2. Unsupervised Time Series Outlier Detection with Diversity-Driven Convolutional EnsemblesDavid Campos, Tung Kieu, Chenjuan Guo, Feiteng Huang et al.VLDB 2022 · 74 citations
  3. Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based ApproachDaichi Amagata, Makoto Onizuka, Takahiro HaraSIGMOD 2021 · 22 citations
  4. METER: A Dynamic Concept Adaptation Framework for Online Anomaly DetectionJiaqi Zhu, Shaofeng Cai, Fang Deng, Beng Chin Ooi et al.VLDB 2024 · 18 citations
  5. TOD: GPU-accelerated Outlier Detection via Tensor OperationsYue Zhao, George H. Chen, Zhihao JiaVLDB 2023 · 10 citations

Related papers

  1. Adaptive Outlier Detection over Data StreamRui Zhu, Mingyuan Jiang, Xiaochun Yang, Baihua Zheng et al.SIGMOD 2026
  2. Multiple Dynamic Outlier-Detection from a Data Stream by Exploiting Duality of Data and QueriesSusik Yoon, Yooju Shin, Jae-Gil Lee, Byung Suk LeeSIGMOD 2021 · 15 citations
  3. Ultrafast Local Outlier Detection from a Data Stream with Stationary Region SkippingSusik Yoon, Jae-Gil Lee, Byung Suk LeeKDD 2020 · 29 citations
  4. MemStream: Memory-Based Streaming Anomaly DetectionSiddharth Bhatia, Arjit Jain, Shivin Srivastava, Kenji Kawaguchi et al.WWW 2022 · 33 citations
  5. Online Detection of Outstanding Quantiles with QuantileFilterYuhan Wu, Aomufei Yuan, Zhouran Shi, Yuanpeng Li et al.ICDE 2024 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines