# An Incremental Local Outlier Detection Method in the Data Stream
## 2 Materials and Methods
### Incremental Outlier Detection  
To follow the nonhomogeneity in data streams, a fixed sliding window with user-specified width is involved in the CLOF, where a new data point has to be continuously inserted into the sliding window, and an obsolete data point has to be continuously deleted from the sliding window simultaneously. In this chapter, the influence of these updates on algorithm complexity is discussed. In the insertion phase of new data \(x_{\mathrm{new}}\), the CNN and CLOF of \(x_{\mathrm{new}}\) are first calculated based on the distance between \(x_{\mathrm{new}}\) and the rest of the data in the sliding window. Then, the affected data objects should be found, and their CNN and CLOF are updated. As shown in Figure 2, for \(k=2\), after the insertion of \(x_{\mathrm{new}}\), the \(\mathrm{kNN}_{2}(5)\) has changed, and data 5 belongs to \(\mathrm{RkNN}_{2}(x_{\mathrm{new}})\), which indicates that the kNN affected data should be found in \(\mathrm{RkNN}_{2}(x_{\mathrm{new}})\). Simultaneously, \(\mathrm{RkNN}\)-affected data contains data 4, 5, and 6, which can be divided into two parts: objects in \(\mathrm{kNN}_{2}(x_{\mathrm{new}})\) (data 4 and 5) and objects that are deleted from the kNN of data in \(\mathrm{RkNN}_{2}(x_{\mathrm{new}})\); for example, data 6 is deleted from the kNN of 5, and data 5 belongs to \(\mathrm{RkNN}_{2}(x_{\mathrm{new}})\). Finally, \(\mathrm{SkNN}\)-affected data contains data 5, 7, and 8. Data 6 has been deleted from \(\mathrm{kNN}_{2}(5)\), which results in the break of the shared neighborhood relationship between data 5 and data 7 and 8. Data 5, 7, and 8 belong to \(\mathrm{RkNN}_{2}(6)\). This indicates that  
Figure 1: Local neighbors in different data distributions. the SkNN-affected data set should be found in the RkNN of \(x_{\text{del}}\). Furthermore, \(x_{\text{del}}\) is the data set that is deleted from the kNN of some objects after the insertion of \(x_{\text{new}}\). As shown in Figure 2, data 6 is the \(x_{\text{del}}\), and it is deleted from \(\text{kNN}_{2}(5)\) after the insertion of data \(x_{\text{new}}\). Therefore, to estimate the algorithm complexity in our incremental update strategy, the Theorems 4-6 are summarized as follows:  
**Theorem 4**. : _After the insertion of new data \(x_{\text{new}}\), the amount of kNN-affected data is \(\left|\text{kNN}\right|_{\text{affected}}=\left|\text{RkNN}(x_{\text{new}})\right|\)._  
Proof. : The kNN-affected objects are those that contain \(x_{\text{new}}\) in their kNN, and \(\left|\text{kNN}\right|_{\text{affected}}\) equals \(\left|\text{RkNN}(x_{\text{new}})\right|\). As demonstrated in the literature [7], \(\left|\text{RkNN}(x_{\text{new}})\right|\leq F=\Theta\Big{(}k2^{D}\sqrt{D} \Big{)}\), where \(F\) is the maximal number of data in kRNN. \(\square\)  
**Theorem 5**. : _After the insertion of new data \(x_{\text{new}}\), the amount of RkNN-affected data is \(\left|\text{RkNN}\right|_{\text{affected}}=\left|\text{kNN}(x_{\text{new}}) \right|+\left|\text{RkNN}(x_{\text{new}})\right|\)._  
Proof. : The RkNN-affected objects contain objects in \(\text{kNN}(x_{\text{new}})\), and objects that are deleted from the kNN of objects in \(\text{RkNN}(x_{\text{new}})\). For objects in \(\text{RkNN}(x_{\text{new}})\), their kNN will include \(x_{\text{new}}\) and will delete one RkNN affected object at the same time. This indicates that the amount of objects that are deleted from the kNN of objects in \(\text{RkNN}(x_{\text{new}})\) equals \(\left|\text{RkNN}(x_{\text{new}})\right|\). Then, \(\left|\text{RkNN}\right|_{\text{affected}}\) equals \(\left|\text{kNN}(x_{\text{new}})\right|+\left|\text{RkNN}(x_{\text{new}})\right| \leq k+F\). \(\square\)  
**Theorem 6**. : _After the insertion of new data \(x_{\text{new}}\), the amount of SkNN-affected data is \(\left|\text{SkNN}\right|_{\text{affected}}=\left|\text{RkNN}(x_{\text{new}}) \right|\cdot\left|\text{RkNN}(x_{\text{del}})\right|\)._  
Proof.