For any two point sets $A,B \subset \mathbb{R}^d$ of size up to $n$, the
Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A}
\min_{b \in B} d_X(a,b)$, where $d_X$ is the underlying distance measure (e.g.,
the Euclidean or Manhattan distance). The Chamfer distance is a popular measure
of dissimilarity between point clouds, used in many machine learning, computer
vision, and graphics applications, and admits a straightforward $O(d n^2)$-time
brute force algorithm. Further, the Chamfer distance is often used as a proxy
for the more computationally demanding Earth-Mover (Optimal Transport)
Distance. However, the \emph{quadratic} dependence on $n$ in the running time
makes the naive approach intractable for large datasets.
We overcome this bottleneck and present the first $(1+\epsilon)$-approximate
algorithm for estimating the Chamfer distance with a near-linear running time.
Specifically, our algorithm runs in time $O(nd \log (n)/\varepsilon^2)$ and is
implementable. Our experiments demonstrate that it is both accurate and fast on
large high-dimensional datasets. We believe that our algorithm will open new
avenues for analyzing large high-dimensional point clouds. We also give
evidence that if the goal is to \emph{report} a $(1+\varepsilon)$-approximate
mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic
time algorithm is unlikely to exist.

提出了一种使用近似算法以几乎线性的运行时间估算 Chamfer 距离的方法，适用于大规模高维数据集，为分析大规模高维点云开辟了新的途径。

一种近线性时间算法的 Chamfer 距离

A Near-Linear Time Algorithm for the Chamfer Distance

Retrieval pipelines commonly rely on a term-based search to obtain candidate
records, which are subsequently re-ranked. Some candidates are missed by this
approach, e.g., due to a vocabulary mismatch. We address this issue by
replacing the term-based search with a generic k-NN retrieval algorithm, where
a similarity function can take into account subtle term associations. While an
exact brute-force k-NN search using this similarity function is slow, we
demonstrate that an approximate algorithm can be nearly two orders of magnitude
faster at the expense of only a small loss in accuracy. A retrieval pipeline
using an approximate k-NN search can be more effective and efficient than the
term-based pipeline. This opens up new possibilities for designing effective
retrieval pipelines. Our software (including data-generating code) and
derivative data based on the Stack Overflow collection is available online.

通过使用 k-NN 检索算法和近似算法，考虑到微妙的词汇相关性，以取代基于词汇的搜索并提高检索效率。

走出常规路线：用 k-NN 搜索替代基于词项检索

Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search

Given two graphs, the graph matching problem is to align the two vertex sets
so as to minimize the number of adjacency disagreements between the two graphs.
The seeded graph matching problem is the graph matching problem when we are
first given a partial alignment that we are tasked with completing. In this
paper, we modify the state-of-the-art approximate graph matching algorithm
"FAQ" of Vogelstein et al. (2015) to make it a fast approximate seeded graph
matching algorithm, adapt its applicability to include graphs with differently
sized vertex sets, and extend the algorithm so as to provide, for each
individual vertex, a nomination list of likely matches. We demonstrate the
effectiveness of our algorithm via simulation and real data experiments;
indeed, knowledge of even a few seeds can be extremely effective when our
seeded graph matching algorithm is used to recover a naturally existing
alignment that is only partially observed.

该论文提出了一种快速的基于图形的相似匹配算法，通过模拟和实际数据实验验证了该算法的有效性，能够从部分观察到的自然存在的对齐中恢复信息。

种子图匹配

Seeded Graph Matching

Latent Dirichlet Allocation models discrete data as a mixture of discrete
distributions, using Dirichlet beliefs over the mixture weights. We study a
variation of this concept, in which the documents' mixture weight beliefs are
replaced with squashed Gaussian distributions. This allows documents to be
associated with elements of a Hilbert space, admitting kernel topic models
(KTM), modelling temporal, spatial, hierarchical, social and other structure
between documents. The main challenge is efficient approximate inference on the
latent Gaussian. We present an approximate algorithm cast around a Laplace
approximation in a transformed basis. The KTM can also be interpreted as a type
of Gaussian process latent variable model, or as a topic model conditional on
document features, uncovering links between earlier work in these areas.

本文研究的是 Latent Dirichlet Allocation 模型的一个变体，将文档混合比重置为 squashed Gaussian 分布，从而实现对以时间、空间、层次结构、社交等方面为特征的文档的建模，同时提出了一个基于 Laplace 近似的转化基础的近似算法以便对隐藏的高斯分布进行有效的近似推断。该 KTM 模型也可以被解释为一种 Gaussian 过程潜变量模型，或基于文档特征的主题模型，在发掘这些领域的早期工作的联系时非常有用。