Abstract: Aiming at the problem that it was  difficult to achieve real time processing of distance-based outlier detection in high speed data stream environments within an effective time, we  proposed a θ-approximate outlier detection algorithm over data stream. The algorithm was based on the local uniformity of object distributions. It constructed a summary structure of local uniform distribution to identify and maintain regional nodes that satisfied  approximate  uniform distribution characteristics. By using the positional  relationship between the query object and these regional nodes, it  estimated the number of neighbors and determined the outlier state of the object under the  guarantee of probability error. Unlike traditional methods that required frequent execution of precise range queries, the algorithm prioritized object state determination through estimating the number of neighbors under probability guarantee, and only performed exact neighbor computation when necessary, thereby reducing the cost of range queries and distance calculations. The experimental results on real and synthetic datasets show that the proposed algorithm  can significantly reduce processing time while maintaining good detection accuracy. The use of local distribution characteristics for probabilistic approximation judgment can effectively improve the real time processing capability of outlier detection in high-speed  data stream environments, providing an efficient and quality guaranteed solution for large-scale data stream management and analysis.

Key words: distance-based outlier detection, data stream, probability error, local uniform distribution