Sets clustering Given a set $S$ of $k$ sets, where $S_k$ is a set of high-dimentional vectors $S_k=\{v_{k_1}...v_{k_{|S_k|}}\}$, s.t the dimension of all vectors is fixed $|v_{k_i}|=l$.
The vectors are outputs from an encoder and the term "similar vectors" refers to pair of vectors with cosine similarity close to one.
We wish to cluster similar sets together, I.e, find a method that given a new set of vectors will find other sets that are close to it.
The size of the sets may differ $|S_k|\neq|S_{k'}|$, and no vector $v_{k_i}$ is present in more than one set.
What methods exist to cluster sets together such that sets with vectors that are close under the inner product will be clustered together?
Currently, we compute the chamfer distance between every two sets (which is not a clustering method, rather a similarity evaluation).
Given a new set, we wish to find similar sets without the need to compute the chamfer to all sets in the dataset.
 A: Your question does not provide enough information to decide between different methods, so I'll just list different known ways to compute a similarity between sets of points. My answer only gives different distances you can compute, not a solution to avoid computing distance between every set of points.
Distribution Distance
A distribution distance outputs a positive scalar $d = D(S_1,S_2)$ which tells you how similar two sets of points are. I will denote $S_1 = \{{x}_1, \dots, {x}_n\}$ the first set with $n$ points and $S_2 = \{{y}_1, \dots, {y}_m\}$ the second set with $m$ points (possibly $m\neq n$).
MMD
The Maximum Mean Discrepancy supposes a symmetric positive definite kernel $k(x,y)$ which returns a similarity measure between two vectors $x,y$. The definition is
$$ \widehat{\mathrm{MMD}}^2(S_1,S_2) = \dfrac{1}{n^2}\sum_{i,j=1}^nk(x_i,x_j) + \dfrac{1}{m^2}\sum_{i,j=1}^mk(y_i,y_j) - \dfrac{2}{nm}\sum_{i,j=1}^{n,m}k(x_i,y_j)$$
Note that the classical energy distance corresponds to the MMD for the kernel $k(x,y) = -\lVert x-y\rVert$. You can plug any popular characteristic kernel in this formula, such as the Rational Quadratic (RQ), Radial Basis Function (RBF) kernel, Laplacian kernel, etc.
In python you can use the shogun library, or the geomloss package. You can also reimplement it yourself, it's not that complicated.
Wasserstein
The wasserstein metric between $S_1$ and $S_2$ transforms a cost $c(x,y)$ on individual points into a cost between distributions (or sets of points). The exact wasserstein distance is hard to compute, but easy to compute approximations exist.
Optimal Transport (OT) losses are known to be similar to MMD-type losses as in this paper.
In python you can compute OT losses between sets of points using the geomloss package which supports GPU.
Friedman-Rafsky Test
This is another distribution-free test. It uses Minimum Spanning Trees between points of $S_1\cup S_2$. For more information, see this paper. In plain english, if points of $S_1$ are often connected to points of $S_2$, the two sets are similar.
Procrustes
If you believe the location, scale and orientation of your points is not important, try finding the optimal translation $\mu$ and rotation $\mathrm{R}$ so that the two sets are the most similar: $S_2 \approx \mathrm{R}(S_1 + \mu) = \tilde{S}_1$. You then use two sample tests on the transformed samples. This means that instead of computing $D(S_1,S_2)$ you compute $D(\tilde{S}_1,S_2)$.
