# Rough Estimator Based Asynchronous Distributed Super Points Detection on High Speed Network Edge
## 4 RE Based Distributed Super Points Detection Algorithm READ
### Estimate Cardinalities of Candidate Super Points  
The LEA at each observation node is used for estimating the cardinality of global candidate super points. A simple way is to send all LEAs at each observation node to the global server, and then merge all LEA of observation nodes on the global server in a \"bit or\" manner to get the global LEA. In this paper, when the operand of \"\(\sum\)\" is the LE or RE set, it means that all LE or RE in the set are merged by outer merging method; when the operand of \"\(\prod\)\" is the LE or RE set, it means that all LE or RE in the set are merged by inner merging method. Merging LEA of all observation nodes on the global server in the way of outer merging is equivalent to sending IP address pairs directly to the global server to update the global LEA. Because LE outer merging guarantees that any bit in the global LEA will remain 1 as long as it is set to 1 at one or more observation nodes. After the global LEA is generated, the cardinalities of global candidate super points can be estimated according to the global LEA. Let \(q\) denote a global candidate super point, \(\mathfrak{B}_{i}^{l}(q)\) denote the LE of \(q\) in the \(i\)-th LEV of the \(t\)-th observation node, i.e., \(\mathfrak{B}_{i}^{l}(q)=\mathbb{L}_{i,i^{\prime}}^{l}\), \(j=\mathbb{h}_{i}^{LEA}(q)\). Using hash functions \(\mathbb{h}_{i}^{LEA}(q)\), it is easy to find these LEs used by \(q\) from the global LEA. Let \(\mathfrak{B}_{i}(q)\) denote the LE associating with \(q\) in the first LEV of the global LEA. Since global LEA is obtained by combining LEA from all observation nodes, \(\mathfrak{B}_{i}(q)=\sum_{l=0}^{m-1}\mathfrak{B}_{i}^{l}(q)\). The \(\hat{u}\) LE of \(q\) on the global LEA are merged into \(\overline{\overline{\mathfrak{B}(q)}}=\prod_{i=0}^{q-1}\mathfrak{B}_{i}(q)\). Let \(\overline{\overline{\mathfrak{B}(q)}}|\) denote the number of bits with value \"1\" in \(\overline{\overline{\mathfrak{B}(q)}}\). The cardinality of \(q\) is estimated based on \(\overline{\overline{\mathfrak{B}(q)}}\) by Equation (1). If the estimated result is larger than the threshold, \(q\) is reported as a super point. Although the above method avoids sending all IP addresses to the global server, it still needs to send the complete LEA to the global server. In order to improve the accuracy of cardinality estimating, the parameters of LEA are set to larger values. For example, when \(\hat{u}=5\), \(\hat{v}=2^{15}\), \(|\mathbb{C}|=2^{14}\), LEA is 320 MB in size. When estimating cardinalities, each observation node needs to send 320 MB of data to the global server. When estimating the cardinality of global candidate super point \(q\), only \(\overline{\overline{\mathfrak{B}(q)}}\) is needed. Based on this principle, READ first sends the global candidate super points to each observation node from the global server, and then each observation node sends these LE relating with candidate super points back to the global server, as shown in Figure 8.  
In Figure 8, \(\mathbb{Q}=\{q_{0},q_{1},q_{2},\cdots,q_{m-1}\}\) denotes the set of global candidate super points, \(\overline{\mathfrak{B}^{l}}\) denotes the set of LE used to estimate cardinalities of global candidate super points in \(\mathbb{Q}\) on the observation node \(l\). For global candidate super point \(q\), there are \(\hat{u}\) LE associating with it, i.e., \(\{\mathfrak{B}_{i}^{l}(q),\mathfrak{B}_{i}^{l}(q),\cdots,\mathfrak{B}_{i-1}^{ l}(q)\}\). READ does not send all of the \(\hat{u}\) LE to the global server, but the result of internal merging, \(\overline{\mathfrak{B}^{l}(q)}=\prod_{i=0}^{\hat{u}-1}\mathfrak{B}_{i}^{l}(q)\).In Figure 8, \(\overline{\mathfrak{B}^{l}}=\{\overline{\mathfrak{B}^{l}(q_{0})},\overline{ \overline{\mathfrak{B}^{l}}(q_{1})},\overline{\overline{\mathfrak{B}^{l}}(q_{2 })},\cdots,\overline{\overline{\mathfrak{B}^{l}}(q_{m-1})}\}\) is the LE set to be sent to the global server on the \(l\)-th observation node.