Fast Detecting Outliers over Online Data Streams
Xianghong Tang, Guohui Li, Gang Chen · 2009
How to mine outliers of online data streams in a short time is an unsolved problem. We propose a new outlier factor metric whose name is the frequent pattern contradiction outlier factor called FPCOF for short. FPCOF can easily measure the degree to which each data instance in data streams is considered as an outlier. In order to compute FPCOF, we construct an outlier detection tree (or OD-tree in short) and design a set of algorithms (ODFP-SW). These algorithms can fast compute FPCOF of new incoming elements by incrementally updating them on the OD-tree, and dynamically maintain the candidate outlier sets and FPCOF of the candidate outliers. The results of experiments show that the proposed method not only can efficiently and accurately mine the outliers in online data streams, but also is more scalable than other existing algorithms.