## 3 Initial Mapping to Line
### Affinity-Based Mapping  
One drawback of the Hilbert-curve cover (even when geographic coordinates are available) is that it ignores the actual edges in the graph. For an illustration, consider using the Hilbert curve to map certain points in an archipelago (or just a small number of islands or peninsulas). The Hilbert curve, unaware of the connectivities, traverses the vertices in a semirandom order, therefore, it may jump from island to island without covering the entire island first. To address this issue, we use an agglomerative hierarchical clustering method, usually called average-linkage clustering We call the method \"affinity clustering\" since it takes into account the affinity of vertices. Informally, every node starts in a singleton cluster of its own and then in several stages we group vertices that are closely connected, hence building a tree of these connections. More precisely, at every stage, each node turns on the connection to its closest neighbor, after which the connected components form clusters. The similarities used in the next level between constructed clusters are computed via some function of the similarities between the elements forming the clusters; in particular, we take the average function for this purpose. Typically attributed to Reference [35], this is reminiscent of a parallel version of [PERSON]'s algorithm for minimum spanning tree where the min operation is replaced by average [36]. The final ordering is produced by sorting the vertex labels produced as follows. Let the label for each vertex be the concatenation of vertex ID strings from the root to the corresponding leaf. Sorting the constructed labels places the vertices under each branch in a contiguous piece on the line. The same guarantee holds recursively, hence the (edge) proximity is preserved well. A pseudocode for this procedure is given in Algorithm 2: Line 15 uses notation \(a\#b\) to denote the concatenation of labels for \(a\) and \(b\). Notice that this pseudocode explains a sequential algorithm, however, the procedure can be efficiently implemented in a few rounds of MapReduce. In fact, our algorithm is very similar to that in Reference [37] but uses Distributed Hash Tables as explained in Reference [38]. In fact, as mentioned therein, an implementation of the connected-components algorithm within the same framework and using the same techniques provides a 20-40 times improvement in running time compared to best previously known algorithms. ```
0: Graph \(G\), (partial) similarity function \(w\)
0: A permutation of vertices
1:\(\mathcal{C}^{0}\leftarrow\{\{v\}\mid v\in V(G)\}\)
2:for\(v\in V(G)\)do
3:\(\ell(v)\gets v\)
4:\(i\gets 0\)
5:repeat
6:for\(s\in\mathcal{C}^{i}\)do
7:\(p(s)\leftarrow\arg\max\limits_{t\in\mathcal{C}^{i}}w(s,t)\)
8:\(\mathcal{C}^{i+1}\leftarrow\emptyset\)
9:for\(t\in\{p(s)\mid s\in\mathcal{C}^{i}\}\)do
10:\(S\gets p^{-1}(t)\)
11:\(S^{\prime}\leftarrow\bigcup_{s\in S}s\)
12:\(\mathcal{C}^{i+1}\leftarrow\mathcal{C}^{i+1}\cup S^{\prime}\)
13:\(r\leftarrow\arg\min\limits_{r^{\prime}\in S^{\prime}}s\)
14:for\(s^{\prime}\in S^{\prime}\)do
15:\(\ell(s^{\prime})\gets r\#\ell(s^{\prime})\)
16:\(i\gets i+1\)
17:until\(|\mathcal{C}^{i}|=|\mathcal{C}^{i-1}|\)
18:\(\pi\leftarrow\) permutation of vertices sorted according to \(\ell\)
19:return\(\pi\)
```  
**Algorithm 2**AffinityOrdering(\(G,w\))  
Intuitively, we expect vertices connected in lower levels (farther from the root) to be closer than those connected in later stages. (See Figure 2 for illustration). In particular, we observed that a graph with several connected components gives an advantage to affinity tree ordering over the ordering produced by Hilbert curve. For this approach to work, we require meaningful distances/similarities between vertices of the graph. Conveniently it does not matter whether we have access to distances or similarity values.