# Rough Estimator Based Asynchronous Distributed Super Points Detection on High Speed Network Edge
## 2 Related Work
### Cardinality Estimation  
Cardinality is an important attribute in network research [14]. At the same time, the calculation of cardinality is also the basis of super points detection [15]. Therefore, this sub section introduces the algorithm of host's cardinality estimating [16].  
There are many cardinality estimating algorithms, such as Probabilistic Counting Statistic Algorithm (PCSA) [17], HyperLogLog algorithm [18], Linear Estimator (LE) algorithm [19] and so on. LE algorithm is widely used in super points detection because of its high accuracy and simple operation.  
Let \(\mathbb{C}\) denote a set of bits and \(|\mathbb{C}|\) denote the number of bits in \(\mathbb{C}\). LE uses \(\mathbb{C}\) to record and estimate the opposite hosts of \(\mathrm{a}\). Each bit in \(\mathbb{C}\) is initially set to zero. For any opposite  
Figure 1: The observation node on network boarder.  
host b, LE maps it to a bit in \(\mathbb{C}\) by using the hash function \(\mathbb{h}^{LE}(\mathbb{b})\) and sets the bit to \(1\). At the end of time window \(\mathcal{T}\), LE uses the following formula to estimate \(|\mathbb{S}^{\mathbb{B}}_{\mathbb{a},\mathcal{T}}|\).  
\[|\mathbb{S}^{\mathbb{B}}_{\mathbb{a},\mathcal{T}}|^{\prime}=-|\mathbb{C}|*log( n_{0}/(|\mathbb{C}|)) \tag{1}\]  
where \(n_{0}\) denotes the number of bits in \(\mathbb{C}\) with value of \(0\). The estimation error of LE is related to \(|\mathbb{S}^{\mathbb{B}}_{\mathbb{a},\mathcal{T}}|\) and the number of counter \(|\mathbb{C}|\). Define the ratio of \(|\mathbb{S}^{\mathbb{B}}_{\mathbb{a},\mathcal{T}}|\) to \(|\mathbb{C}|\) as a load factor, marked \(\mathfrak{L}\). The estimated standard deviation of LE is \(\sqrt{\frac{(e^{\mathfrak{L}}-\mathfrak{L}-1)}{\mathbb{C}}}\).  
When \(|\mathbb{S}^{\mathbb{B}}_{\mathbb{a},\mathcal{T}}|\) is determined, the larger \(|\mathbb{C}|\) is, the higher the estimation accuracy of LE is. However, the larger \(|\mathbb{C}|\), the more memory space LE occupies, and the longer time it takes to estimate the cardinality.  
In order to compensate for the deficiency of LE, [PERSON] et al. (2018) proposed a lightweight rough estimator (RE). RE only takes eight bits to determine whether \(\mathbb{a}\) is a candidate super point. At initialization, RE sets all eight bits to \(0\). For each opposite host b of \(\mathbb{a}\), RE maps b to a random integer \(\mathbb{\hat{b}}\) between \(0\) and \(2^{32}-1\) using hash function \(\mathbb{h}^{rand}(\mathbb{b})\), and then compares the lowest significant bit of \(\mathbb{\hat{b}}\) with a real number \(\tau\). The lowest significant bit is the position of the first bit \"\(1\)\" starting from the right. For example, the binary formatter of integer \(200\) is \"\(11001000\)\", its lowest significant bit is \(3\). Let \(\mathcal{R}^{0}(x)\) denote the lowest significant bit of integer \(\mathbb{x}\). \(\tau\) is used to determine whether update a bit. The definition of \(\tau\) is as follows.  
\[\tau=log2(\theta/\delta) \tag{2}\]  
If \(\mathcal{R}^{0}(\mathbb{\hat{b}})\geq\tau\), RE maps b to one of eight bits using a hash function and sets the bit to \(1\). Denote this hash function as \(\mathbb{h}^{RE}(\mathbb{b})\). When the number of bits with a value of \(1\) is greater than or equal to \(3\), RE determines b as a candidate super point. As a lightweight estimator, RE can quickly determine candidate super point, but it cannot accurately estimate the cardinality. [PERSON] et al. (2018) used RE as a preliminary screening tool to reduce the range of candidate super points, and combined with LE to realize real-time detection of super points under a sliding time window. A detailed analysis of RE can be found in ([PERSON] et al., 2018).