# Decentralized Mechanism for Edge Node Allocation in Access Network: An Experimental Evaluation
## 2 Methodology
### Parallel/Distributed K-Means  
Apache Spark [20] is a powerful data engine designed for the efficient management of large-scale datasets. It is engineered to provide the necessary computational speed, scalability, and flexibility for complex data analysis tasks. A key distinction between Spark and MapReduce lies in Spark's ability to process and retain data in its memory across multiple computational steps, avoiding the need for repeated disk I/O operations. This in-memory processing capability significantly enhances Spark's processing speed compared with traditional MapReduce frameworks. Apache Spark also offers a unique data structure, i.e., DataFrame, which defines a distributed collection of data organized into named columns, akin to a table in a relational database. DataFrames in Spark provide a higher-level abstraction over the Resilient Distributed Dataset (RDD), offering an optimized framework for distributed data processing. In contrast to RDD, DataFrames possess a schema, which involves the storage of metadata relating to the data structure; this schema defines the column names and data types, which facilitates Spark to perform optimizations such as predicate pushdown or project pruning. First, when a DataFrame operation is performed, Spark constructs a logical plan, which is an abstract representation of the computation. Then, the catalyst optimizer applies various rule-based and cost-based optimizations to produce an optimized physical plan that specifies how the computation will be executed across the computing cluster. As DataFrames are distributed across thecluster environment in the form of partitions, each partition is a subset of the DataFrames' data. As a result, Spark ensures that transformations on DataFrames (map, filter operations) are applied to each partition in parallel, leveraging the distributed nature of the data. However, these transformations are lazy, i.e., they are not executed immediately, but build a logical plan as actions that trigger the execution of the plan. We consider a DataFrame representing a large dataset, \(D\), with columns \(c_{1},c_{2},\dots,c_{n}\), where each \(c_{i}\) is a vector of features in a multi-dimensional space. In the K-Means algorithm, we seek to partition this dataset into \(K\) clusters by minimizing the within-cluster sum of squares (WCSS). For a given cluster, \(C_{j}\), the centroid, \(\mu_{j}\), is computed as the mean of all points, which can be expressed as:  
\[\mu_{j}=\frac{1}{|C_{j}|}\sum_{\mathbf{x}_{i}\in C_{j}}\mathbf{x}_{i} \tag{3}\]  
K-Means aims to minimize the sum described in (1) across all clusters. In Spark, this can be efficiently executed across the computing cluster by representing dataset \(D\) as a DataFrame and, for each data point, \(x_{i}\), determining the closest centroid, \(\mu_{j}\), as we can observe in Algorithm 1. This operation is distributed across the partitions of the DataFrame, where each partition computes the closest centroid for its subset of data points and, after assigning all points to their closest centroids, recomputes the centroids by making a generalization of the centroids of each cluster. This involves filtering the DataFrame by cluster assignment (i.e., grouping by cluster ID) and then calculating the mean of the points in each cluster. In Spark, this is achieved through a combination of groupBy and aggregation operations over the DataFrame. Finally, the WCSS is computed by summing the squared distances of points from their assigned centroids. The workflow is described in Figure 2.  
\[\text{WCSS}=\sum_{x_{i}\in D}\left\|x_{i}-\mu_{\text{closest\_ centroid}(x_{i})}\right\|^{2} \tag{4}\]  
This operation is performed by applying a map operation to calculate the squared distance for each point, followed by a reduction to sum these values across the entire dataset.