Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-2026

Abstract

Continuous distance-based outlier detection in streaming data poses significant challenges and has a wide range of practical applications. Traditional threshold-based methods perform well under stable streaming conditions, where fixed parameters remain effective. However, they often struggle with dynamic data distributions and high stream speeds, leading to suboptimal performance, limited control over the number of returned outliers, and failure to meet real-time detection requirements. To address these issues, this paper introduces a novel Recall and Proportion-Aware Outlier Detection (RPA-OD) query. In RPA-OD, ρ defines a distance relaxation that enables real-time outlier detection. Specifically, objects with fewer than k neighbors within the distance threshold r'∈ (r, (1+ρ) ⋅ r] might be classified as ρ-inliers. This relaxation introduces a trade-off between recall and efficiency, allowing the system to adapt under varying streaming conditions. We propose efficient algorithms to support RPA-OD in data streams, leveraging several novel data structures developed as part of this study. Extensive experiments on five real-world datasets show that RPA-OD significantly improves data throughput, provides precise control over the number of outliers detected, and consistently ensures real-time processing performance.

Keywords

Outlier Detection, Data Stream, Recall and Proportion-Aware

Discipline

Artificial Intelligence and Robotics | Databases and Information Systems

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the ACM on Management of Data

Volume

4

Issue

3

First Page

1

Last Page

26

ISSN

2836-6573

Identifier

10.1145/3802007

Publisher

Association for Computing Machinery (ACM)

Additional URL

https://doi.org/10.1145/3802007

Download

Share

COinS