## 5 Sensor-Stream Reduction
), we use \(\mathbf{\Psi}_{\mathrm{central}}\) and \(\mathbf{\Psi}_{\mathrm{random}}\) to represent the central and random elements choice, respectively. The \(\mathbf{\Psi}_{\mathrm{central}}\) sample reduction process is present in Algorithm 2. Analyzing the Algorithm 2 we have:  
**Line 2**: Executes in \(O(|\mathbf{V}|\ \log|\mathbf{V}|)\);
**Lines 11-15**: Define the inner loop that determines the number of elements at each histogram class of the resulting sample, considering \(H_{cn}\) as the number of histogram class and \(n^{\prime}_{col_{i}}\) as the columns in sampled histograms, where \(0<i\leq H_{cn}\). The \(\sum_{i}^{H_{cn}}n^{\prime}_{col_{i}}=|\mathbf{V}^{\prime}|\), we have that this inner loop executes in \(O(|\mathbf{V}^{\prime}|)\) steps. **Lines 7-20**: Define the outer loop in which the input data is read and the sample elements are chosen. Because the inner loop is executed only when condition in line 8 is satisfied, the overall complexity of the outer loop is \(O(|\mathbf{V}|)+O(|\mathbf{V}^{\prime}|)=O(|\mathbf{V}|+|\mathbf{V}^{\prime}|)\), since we have an interleaved execution. Let \(n_{col_{i}}\) be the columns in original histograms, where \(0<i\leq H_{cn}\). Basically, before evaluating the condition of Line 8, \(n_{col_{i}}\) is accounted and \(|\mathbf{V}|/H_{cn}\) interactions are executed. Whenever this condition is satisfied, \(n^{\prime}_{col_{i}}\) is built and \(|\mathbf{V}^{\prime}|/H_{cn}\) interactions are executed (Lines 11-15). In order to build the complete histogram, we must cover all classes (\(H_{cn}\)), then we have \(H_{cn}\left(|\mathbf{V}|+|\mathbf{V}^{\prime}|\right)/H_{cn}=|\mathbf{V}|+| \mathbf{V}^{\prime}|\). **Line 21**: Re-sorts the sample in \(O(|\mathbf{V}^{\prime}|\ \log|\mathbf{V}^{\prime}|)\). **Line 22**: Re-sorts the sample in \(O(|\mathbf{V}^{\prime}|\ \log|\mathbf{V}^{\prime}|)\). **Line 23**: Re-sorts the sample in \(O(|\mathbf{V}^{\prime}|\ \log|\mathbf{V}^{\prime}|)\). **Line 24**: Re-sorts the sample in \(O(|\mathbf{V}^{\prime}|\ \log|\mathbf{V}^{\prime}|)\). **Line 25**: Re-sorts the sample in \(O(|\mathbf{V}^{\prime}|\ \log|\mathbf{V}  
Thus, the overall complexity is  
\[O(|\mathbf{V}|\,\log|\mathbf{V}|)+O(|\mathbf{V}|+|\mathbf{V}^{\prime}|)+O(| \mathbf{V}^{\prime}|\,\log|\mathbf{V}^{\prime}|)=O(|\mathbf{V}|\,\log|\mathbf{V}|)\]  
since \(|\mathbf{V}^{\prime}|\leq|\mathbf{V}|\). The sorting step is necessary, because, in our case, to build the histogram, we need the elements to be sorted, so that we always get the correct elements of \(\mathbf{V}^{\prime}\). The space complexity is \(O(|\mathbf{V}|+|\mathbf{V}^{\prime}|)=O(|\mathbf{V}|)\) because we store the original sensor-stream and the resulting sample. Since every source node sends its sample stream towards the sink, the communication complexity is \(O(|\mathbf{V}^{\prime}|\,D)\), where \(D\) is the largest route (in hops) in the network. ```
Data: \(\mathbf{V}\) - original sensor-stream Data: \(|\mathbf{V}^{\prime}|\) - resulting sample size Result: \(\mathbf{V}^{\prime}\) - resulting sample set begin \(Sort(\mathbf{V})\) \(wid\leftarrow\) \"Histogram's class width\" \(fst\gets 0\) {first index of histogram class} \(n_{col}\gets 0\) {number of elements per columns in \(\mathbf{V}\)} \(w\gets 0\) for\(k\gets 0\)to\(|\mathbf{V}|-1\)do if\(\mathbf{V}[k]>\mathbf{V}[fst]+wid\)or\(k=|\mathbf{V}|-1\)then \(n^{\prime}_{col}\leftarrow\lceil n_{col}\,|\mathbf{V}^{\prime}|/|\mathbf{V}|\) {number of elements per columns in \(\mathbf{V}^{\prime}\)} \(index\gets fst+\lceil(n_{col}-n^{\prime}_{col})/2\rceil\) for\(l\gets 0\)to\(n^{\prime}_{col}\)do \(\mathbf{V}^{\prime}[w]\leftarrow\mathbf{V}[index]\) \(w\gets w+1\) \(index\gets nextIndex\)  end for \(n_{col}\gets 0\) \(fst\gets k\)  end for \(n_{col}\gets n_{col}+1\) \(Sort(\mathbf{V}^{\prime})\) {according to the original order}
```  
**Algorithm 2**Pseudo-code of \(\mathbf{\Psi}_{\mathrm{central}}\) sampling reduction.