# Well-Separated Pair Decompositions for High-Dimensional Datasets
## 1 Introduction  
Given a set of points \(S\subset\mathbb{R}^{d}\), \(|S|=n\), a well-separated pair decomposition (WSPD) can be seen as a compressed representation for approximating \(\binom{n}{2}\) pairwise distances of \(n\) points from \(S\) into \(O(n)\) space, where the dimension \(d\) is considered a constant. The formal definition of a WSPD will be given in Section 2. A WSPD can also be seen as a clustering approach, e.g., a WSPD is a partition of the \(\binom{n}{2}\) edges of the complete Euclidean graph into \(O(n)\) subsets. This decomposition was first introduced in a seminal paper [1] by [PERSON] and [PERSON] in 1995. It has been shown in [1] that the size of a WSPD, when computed by their algorithm, is exponential in \(d\). Hence, it has never been used in practice for dimensions larger than three. However, a WSPD has been shown to be useful in many different applications. It is known that a WSPD can be used to efficiently solve a number of proximity problems [2], such as the closest pair problem, the all-nearest neighbors problem, etc. It is also known that a WSPD directly induces a \(t\)-spanner of a point set or provides a \((1+\varepsilon)\) --approximation of the Euclidean minimum spanning tree. The authors in [3] used a WSPD to compute approximate energy-efficient paths in radio networks. Their algorithm reduced the complexity of computing such paths to \(O(1)\) by moving most of the computation to the pre-processing stage by precomputing a template path for each pair of sets compressing the pairwise distances. Since a WSPD proved to be an essential decomposition for different important problems, in this paper, I investigate to what extent a WSPD can be helpful for situations where the input \(S\subset\mathbb{R}^{d}\) and the dimension \(d\) is much larger than two or three. On the technical side, a WSPD of a set of points \(S\subset\mathbb{R}^{d}\) is represented by a sequence of pairs of sets \((A_{i},B_{i})\), \(i=1,\ldots,k\), called dumbbells, such that (i) for every two distinct points \(a,b\in S\) there exists a unique dumbbell \((A_{i},B_{i})\) such that \(a\in A_{i},b\in B_{i}\); (ii) thedistances between points in \(A_{i}\) and \(B_{i}\) are approximately equal; (iii) the distances between points in \(A_{i}\) or points in \(B_{i}\) are much smaller than the distances between points in \(A_{i}\) and \(B_{i}\). As stated before, the size of a WSPD, i.e., the number of dumbbells, is known to grow exponentially with the dimension \(d\). Hence, instead of computing a WSPD directly on \(S\subset\mathbb{R}^{d}\), I first propose to transform the points in \(S\) with a nonlinear function \(f_{\theta}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d^{\prime}}\), \(d^{\prime}=2\) or \(d^{\prime}=3\), where \(\theta\) denotes the set of learnable function parameters. The parameters \(\theta\) are determined such that the function \(f_{\theta}\) preserves the properties of \(S\) that are important for a WSPD, e.g., preserves pairwise distances for points in \(S\). If the function \(f_{\theta}\) manages to preserve most of the important information for a WSPD, there is hope that the WSPD computed on the mapped points \(f_{\theta}(S)\subset\mathbb{R}^{d^{\prime}}\), \(d^{\prime}=2\) or \(d^{\prime}=3\), where the size of the WSPD is \(O(n)\), will output \"dumbbells\" that are meaningful even for the original input \(S\). If this is the case, the reconstructed dumbbells should continue to be \"dumbbell-shaped\" in the original space. In practice, some of the reconstructed dumbbells can become \"bad\" because they do not approximate the distances in any practical sense. However, I will show that the number of \"bad\" dumbbells is negligible in practice. Moreover, such \"bad\" dumbbells can be easily refined without significantly increasing the total number of dumbbells. One tool I employ might be of independent interest: I implemented a WSPD following the nontrivial algorithm of the partial fair-split tree that guarantees the construction time of \(O(n\log n)\) and a WSPD of \(O(n)\) size.