# Heterogeneous Distributed Big Data Clustering on Sparse Grids
## 3 Estimating Densities on Sparse Grids
### Sparse Grids  
As this work focuses on the sparse grid clustering algorithm and not on the basic sparse grid method, we only introduce the concepts required to understand the core algorithms of sparse grid clustering. For further information and in-depth explanations, we refer to the overview by [PERSON] and [PERSON] (2007) which follows the same notations. The core ideas include a spatial discretization of the (normalized) feature space, enabled by an incremental, adaptive, hierarchical formulation of underlying basis functions in one dimension. Its extension to arbitrary-dimensional settings can be truncated to keep the effort low. A \(d\)-dimensional grid can be defined on the unit hypercube \([0,1]^{d}\) with an equidistant mesh width \(h_{n}=2^{-n}\) for a discretization level \(n\in\mathbb{N}\) and, therefore, 2 nd grid points. With basis functions centered at the grid points, a corresponding function space is spanned by the linear combinations of the basis functions. We call this a full grid approach. Full grids can be represented in a hierarchical basis. From this representation, it is a small step to sparse grids. The hierarchical approach constructs a final grid by superimposing a set of subgrids. First, we define an index set that is used to enumerate the grid points on the \(d\)-dimensional subgrids of discretization level \(\mathbf{l}\in\mathbb{N}^{d}\):  
\[I_{\mathbf{l}}:=\{(i_{1},\ldots,i_{d}):0<i_{k}<2^{I_{k}},i_{k}\text{ odd}\}. \tag{2}\]  
In this work, we employ hat functions as basis functions. The scaled and translated 1-D hat functions are defined as  
\[\phi_{l,i}(x):=\max(0,1-|2^{l}x-i|). \tag{3}\]  
For \(d>1\), we use a tensor-product approach:  
\[\phi_{\mathbf{l},\mathbf{i}}(\mathbf{x}):=\prod_{j=1}^{d}\phi_{l_{j},i_{j}}(x_ {j}). \tag{4}\]  
Given an index set \(I_{\mathbf{l}}\) and the basis functions \(\phi_{\mathbf{l},\mathbf{i}}\), we can define the subspaces  
\[W_{\mathbf{l}}:=\text{span}\{\phi_{\mathbf{l},\mathbf{i}}:\mathbf{i}\in I_{ \mathbf{l}}\}. \tag{5}\]  
The subgrids and their grid points \(x_{\mathbf{l},\mathbf{i}}:=(i_{1}h_{l_{1}},\ldots,i_{d}h_{l_{d}})\) for the subspaces \(W_{(1,1)}\ldots W_{(3,3)}\) are displayed in Figure 1(a) for a 2-D grid. With the direct sum \(\bigoplus\), a full grid of discretization level \(n\in\mathbb{N}\) in the hierarchical basis can be defined as  
\[V_{n}:=\bigoplus_{|\mathbf{l}|_{\infty}\leq n}W_{\mathbf{l}}. \tag{6}\]  
Figure 3 shows how a 1-D grid is represented in the standard (nodal) basis (Figure 2(a)) and the hierarchical basis (Figure 2(b)). Sparse grids are based on the observation that for sufficiently smooth functions only a small additional interpolation error is introduced if certain grid points are removed issue of dimensionality. As a result, the sparse grid function space \(V_{n}^{(1)}\) is constructed from a different set of subspaces:  
\[V_{n}^{(1)}:=\bigoplus_{|\mathbf{i}|_{1}\leq n+d-1}W_{\mathbf{i}}. \tag{7}\]  
Figure 2 shows how a 2-D sparse grid is constructed from subgrids that correspond to the subspaces of the grid. A sparse grid function \(f\in V_{n}^{(1)}\) is given as  
\[f(\mathbf{x})=\sum_{|\mathbf{i}|_{1}\leq n+d-1}\sum_{\mathbf{i}\in\mathbf{I}} \alpha_{\mathbf{i},\mathbf{i}}\phi_{\mathbf{i},\mathbf{i}}(\mathbf{x})=\sum_{ j=1}^{N}\alpha_{j}\phi_{j}(\mathbf{x})\;, \tag{8}\]  
where we sum up all \(N\) weighted basis functions in some order, and where \(N\) denotes the total number of grid points. Since our algorithms iterate the basis functions linearly, we use the simplified notation when the algorithms are presented. The coefficients \(\alpha_{\mathbf{i},\mathbf{i}}\) are usually referred to as surpluses. Figure 3: The nodal and the sparse grid in Figure 2(a),b both have discretization level \(l=3\) and are equal for \(d=1\). Both use hat functions \(\phi_{l,l}\) as basis functions, but in a nodal and in a hierarchical formulation. Note that sparse grids employ less grid points compared to full grids of the same level for \(\mathrm{d}\geq 2\) (see Figure 2).