快速可靠的K-最近邻图算法比在许多数据处理技术中广泛使用，这比以往更重要。本文介绍了Wei Dong等人的启发式“NN-DESCENT”算法的运行时优化的C实现。对于L2距离度量。解释了各种实现优化，从而提高了低维和高维数据集的性能。优化以加快选择哪个DataPoint对来评估用于对低维数据集的影响距离。提出了一种利用NN-DESCENT的迭代性质来重新排序存储器中的数据的启发式，这是能够更好地利用局部性，从而改善运行时。对L2距离度量的限制允许使用阻塞距离评估，这显着提高了高维数据集的性能。结合优化产生了一种实现，这显着优于所有被考虑的数据集的广泛使用的NN-DESCEND。例如，流行的Mnist手写数字数据集上的运行时会减半。

t-SNE remains one of the most popular embedding techniques for visualizing high-dimensional data. Most standard packages of t-SNE, such as scikit-learn, use the Barnes-Hut t-SNE (BH t-SNE) algorithm for large datasets. However, existing CPU implementations of this algorithm are inefficient. In this work, we accelerate the BH t-SNE on CPUs via cache optimizations, SIMD, parallelizing sequential steps, and improving parallelization of multithreaded steps. Our implementation (Acc-t-SNE) is up to 261x and 4x faster than scikit-learn and the state-of-the-art BH t-SNE implementation from daal4py, respectively, on a 32-core Intel(R) Icelake cloud instance.

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

The accuracy of k-nearest neighbor (kNN) classification depends significantly on the metric used to compute distances between different examples. In this paper, we show how to learn a Mahalanobis distance metric for kNN classification from labeled examples. The Mahalanobis metric can equivalently be viewed as a global linear transformation of the input space that precedes kNN classification using Euclidean distances. In our approach, the metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. As in support vector machines (SVMs), the margin criterion leads to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our approach requires no modification or extension for problems in multiway (as opposed to binary) classification. In our framework, the Mahalanobis distance metric is obtained as the solution to a semidefinite program. On several data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification. Sometimes these results can be further improved by clustering the training examples and learning an individual metric within each cluster. We show how to learn and combine these local metrics in a globally integrated manner.

本文研究了分层聚类问题，其中目标是生产一种在数据集的变化尺度上表示集群的树形图。我们提出了用于设计并行分层凝聚聚类（HAC）算法的Parchain框架，并使用该框架，我们获得了全面连锁，平均联系和病房的联动标准的新颖平行算法。与最先前的并行HAC算法相比，这需要二次存储器，我们的新算法仅需要线性存储器，并且可以扩展到大数据集。 PARCHAIN基于我们最近邻的链算法的并行化，并使多个群集能够在每一轮上合并。我们介绍了两个关键优化，这对于效率至关重要：范围查询优化，减少查找群集的最近邻居所需的距离计算数，以及存储可能重复使用的先前计算的距离子集的缓存优化。通过实验，我们表明，我们的高度优化实现，使用48个核心，通过双向超线程实现5.8--110.1倍的加速，通过最先进的并行HAC算法，实现了13.75--54.23倍的自相对加速。与最先进的算法相比，我们的算法较少的空间少于237.3倍。我们的算法能够扩展到具有数百万点的数据集大小，现有算法无法处理该算法。

维数减少方法发现了巨大的应用程序作为不同科学领域的可视化工具。虽然存在许多不同的方法，但它们的性能通常不足以提供对许多当代数据集的快速深入了解，并且无监督的使用方式可防止用户利用数据集探​​索和微调可视化质量的细节方法。我们呈现开花，一种高性能半监督维度减少软件，用于具有数百万个单独的数据点的高维数据集的交互式用户可信可视化。 Blossom在GPU加速实施的EMBEDSOM算法的实现上，由几个基于地标的算法补充，用于将无监督模型学习算法与用户监督联系起来。我们展示了开花在现实数据集上的应用，在那里它有助于产生高质量的可视化，该可视化包含用户指定的布局并专注于某些功能。我们认为，半监督的维度减少将改善单细胞细胞谱系等科学领域的数据可视化可能性，并为数据集勘探和注释提供了新的方向的快速有效的基础方法。

基于拓扑的维度减少方法，如T-SNE和UMAP，已经看到了高维数据的成功和普及。这些方法具有强大的数学基础，基于直觉，即低维度的拓扑应接近高维度。鉴于初始拓扑结构是算法成功的前兆，这自然提出了问题：是什么使得维数减少的“良好”拓扑结构？深入了解这将使我们能够设计更好的算法，该算法考虑到本地和全局结构。在专注于UMAP的本文中，我们研究节点连接（k最近邻居与互相k离邻居）和相对邻域（相邻通孔邻居）的影响对维数减少。我们通过关于4标准图像和文本数据集的广泛消融研究探索这些概念; Mnist，Fmnist，20ng，Ag，减少2和64个尺寸。我们的研究结果表明，连接局部邻域（PATH邻居）的灵活方法更加精致的连接（相互K最近邻居）的概念，可以实现比下游测量的默认UMAP更好的表示聚类性能。

Similarity search finds application in specialized database systems handling complex data such as images or videos, which are typically represented by high-dimensional features and require specific indexing structures. This paper tackles the problem of better utilizing GPUs for this task. While GPUs excel at data-parallel tasks, prior approaches are bottlenecked by algorithms that expose less parallelism, such as k-min selection, or make poor use of the memory hierarchy.We propose a design for k-selection that operates at up to 55% of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5× faster than prior GPU state of the art. We apply it in different similarity search scenarios, by proposing optimized design for brute-force, approximate and compressed-domain search based on product quantization. In all these setups, we outperform the state of the art by large margins. Our implementation enables the construction of a high accuracy k-NN graph on 95 million images from the Yfcc100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs. We have open-sourced our approach 1 for the sake of comparison and reproducibility.

TSNE和UMAP是两个最流行的降低算法，因为它们的速度和可解释的低维嵌入。但是，尽管已经尝试改善TSNE的计算复杂性，但现有方法无法以UMAP的速度获得TSNE嵌入。在这项工作中，我们表明，通过将两种方法组合为单一方法，这确实是可能的。我们从理论上和实验上评估了TSNE和UMAP算法中参数的完整空间，并观察到单个参数（归一化）负责在它们之间切换。反过来，这意味着可以切换大多数算法差异而不会影响嵌入。我们讨论了这对基于UMAP框架的几种理论主张的含义，以及如何将它们与现有的TSNE解释调和。基于我们的分析，我们提出了一种新的降低性降低算法GDR，该算法结合了先前来自TSNE和UMAP的不兼容技术，并可以通过更改归一化来复制任何一种算法的结果。作为进一步的优势，GDR比可用的UMAP方法更快地执行优化，因此比可用的TSNE方法快的数量级。我们的实施是使用传统的UMAP和TSNE库的插件，可以在github.com/andrew-draganov/gidr-dun上找到。

在机器学习中调用多种假设需要了解歧管的几何形状和维度，理论决定了需要多少样本。但是，在应用程序数据中，采样可能不均匀，歧管属性是未知的，并且（可能）非纯化；这意味着社区必须适应本地结构。我们介绍了一种用于推断相似性内核提供数据的自适应邻域的算法。从本地保守的邻域（Gabriel）图开始，我们根据加权对应物进行迭代率稀疏。在每个步骤中，线性程序在全球范围内产生最小的社区，并且体积统计数据揭示了邻居离群值可能违反了歧管几何形状。我们将自适应邻域应用于非线性维度降低，地球计算和维度估计。与标准算法的比较，例如使用K-Nearest邻居，证明了它们的实用性。

K-Nearest邻居搜索是各种应用程序中的基本任务之一，层次可导航的小世界（HNSW）最近在大规模云服务中引起了人们的注意，因为它在提供快速搜索的同时很容易扩展数据库。另一方面，将可编程逻辑和单个板上的可编程逻辑模块结合在一起的计算存储设备（CSD）变得流行，以解决现代计算系统的数据带宽瓶颈。在本文中，我们提出了一个计算存储平台，该平台可以加速基于SMARTSSSD CSD的基于图形的最近的邻居搜索算法。为此，我们更修改算法在硬件上更适合，并使用基于HLS和RTL的方法实现两种类型的加速器，并采用各种优化方法。此外，我们扩展了提议的平台，以拥有4个SMARTSSS，并应用图形并行性以进一步提高系统性能。结果，拟议的计算存储平台在258.66W的功率耗散时，SIFT1B数据集的每秒吞吐量达到75.59个查询，该数据集的功率耗散为12.83倍，比常规CPU和GPU和GPU更快，更快的10.43 x和10.43 x和24.33 x - 基于基于的服务器平台。借助多稳定的存储和自定义加速能力，我们相信所提出的计算存储平台是针对成本敏感的云数据中心的有前途的解决方案。

最近，Graph神经网络（GNNS）已成为聚光灯作为强大的工具，可以有效地在图形结构化数据上执行各种推理任务。随着现实图表的大小继续扩展，GNN训练系统面临可扩展性挑战。分布式培训是一种流行的方法，可以通过扩展CPU节点来应对这一挑战。但是，对基于磁盘的GNN培训的关注不多，该培训可以通过利用NVME SSD等高性能存储设备来以更具成本效益的方式扩展单节点系统。我们观察到，主内存和磁盘之间的数据移动是基于SSD的训练系统中的主要瓶颈，并且常规的GNN训练管道是不错的选择，而无需考虑此开销。因此，我们提出了Ginex，这是第一个基于SSD的GNN训练系统，可以在单台计算机上处​​理数十亿个图形数据集。受到编译器优化的检查员执行模型的启发，Ginex通过分开样品和收集阶段来重组GNN训练管道。这种分离使Ginex能够实现一种可证明的最佳替换算法，即被称为Belady的算法，用于存储器中的Caching特征向量，该算法是I/O访问的主要部分。根据我们对40亿尺度图数据集的评估，Ginex平均比SSD扩展的Pytorch几何得出了2.11倍的训练吞吐量（最大最高2.67倍）。

索引是支持大型数据库中有效查询处理的有效方法。最近，已积极探索了替代或补充传统索引结构的学习指数的概念，以降低存储和搜索成本。但是，在高维度空间中准确有效的相似性查询处理仍然是一个开放的挑战。在本文中，我们提出了一种称为LIMS的新型索引方法，该方法使用数据群集，基于枢轴的数据转换技术和学习的索引来支持度量空间中的有效相似性查询处理。在LIM中，将基础数据分配到簇中，使每个群集都遵循相对均匀的数据分布。数据重新分布是通过利用每个集群的少量枢轴来实现的。类似的数据被映射到紧凑的区域，而映射的值是完全顺序的。开发机器学习模型是为了近似于磁盘上每个数据记录的位置。有效的算法设计用于基于LIMS的处理范围查询和最近的邻居查询，以及具有动态更新的索引维护。与传统索引和最先进的学习索引相比，对现实世界和合成数据集的广泛实验证明了LIM的优势。

State-of-the-art algorithms for Approximate Nearest Neighbor Search (ANNS) such as DiskANN, FAISS-IVF, and HNSW build data dependent indices that offer substantially better accuracy and search efficiency over data-agnostic indices by overfitting to the index data distribution. When the query data is drawn from a different distribution - e.g., when index represents image embeddings and query represents textual embeddings - such algorithms lose much of this performance advantage. On a variety of datasets, for a fixed recall target, latency is worse by an order of magnitude or more for Out-Of-Distribution (OOD) queries as compared to In-Distribution (ID) queries. The question we address in this work is whether ANNS algorithms can be made efficient for OOD queries if the index construction is given access to a small sample set of these queries. We answer positively by presenting OOD-DiskANN, which uses a sparing sample (1% of index set size) of OOD queries, and provides up to 40% improvement in mean query latency over SoTA algorithms of a similar memory footprint. OOD-DiskANN is scalable and has the efficiency of graph-based ANNS indices. Some of our contributions can improve query efficiency for ID queries as well.

A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, classification, graph learning, and nearest neighbor search. For these tasks, it is critical to build graphs which are sparse yet still representative of the underlying data. The benefits of sparsity are twofold: firstly, constructing dense graphs is infeasible in practice for large datasets, and secondly, the runtime of downstream tasks is directly influenced by the sparsity of the similarity graph. In this work, we present $\textit{Stars}$: a highly scalable method for building extremely sparse graphs via two-hop spanners, which are graphs where similar points are connected by a path of length at most two. Stars can construct two-hop spanners with significantly fewer similarity comparisons, which are a major bottleneck for learning based models where comparisons are expensive to evaluate. Theoretically, we demonstrate that Stars builds a graph in nearly-linear time, where approximate nearest neighbors are contained within two-hop neighborhoods. In practice, we have deployed Stars for multiple data sets allowing for graph building at the $\textit{Tera-Scale}$, i.e., for graphs with tens of trillions of edges. We evaluate the performance of Stars for clustering and graph learning, and demonstrate 10~1000-fold improvements in pairwise similarity comparisons compared to different baselines, and 2~10-fold improvement in running time without quality loss.

训练机学习（ML）算法是一个计算密集型过程，由于反复访问大型培训数据集，经常会陷入内存。结果，以处理器为中心的系统（例如CPU，GPU）遭受了内存单元和处理单元之间的昂贵数据移动，这会消耗大量的能量和执行周期。以内存为中心的计算系统，即具有内存（PIM）功能，可以减轻此数据运动瓶颈。我们的目标是了解现代通用PIM体系结构加速ML培训的潜力。为此，我们（1）在现实世界通用PIM体系结构上实现了几种代表性的经典ML算法（即线性回归，逻辑回归，决策树，K-均值聚类），（2）严格评估并表征它们在准确性，性能和缩放方面以及（3）与CPU和GPU上的对应物实现相比。我们对具有2500多个PIM核心的真实内存计算系统的评估表明，当PIM硬件在必要的操作和数据类型上，通用PIM架构可以极大地加速内存的ML工作负载。例如，我们对决策树的PIM实施比8核Intel Xeon上的最先进的CPU版本$ 27 \ times $ $，并且比最先进的GPU快$ 1.34 \ times $ $ NVIDIA A100上的版本。我们在PIM上的K-Means聚类分别为$ 2.8 \ times $和$ 3.2 \ times $ $，分别是最先进的CPU和GPU版本。据我们所知，我们的工作是第一个评估现实世界中PIM架构的ML培训的工作。我们以关键的观察，外卖和建议结束，可以激发ML工作负载的用户，PIM架构的程序员以及未来以内存计算系统的硬件设计师和架构师。

我们讨论集群分析的拓扑方面，并表明在聚类之前推断数据集的拓扑结构可以大大增强群集检测：理论论证和经验证据表明，聚类嵌入向量，代表数据歧管的结构，而不是观察到的特征矢量他们自己是非常有益的。为了证明，我们将流形学习方法与基于密度的聚类方法DBSCAN结合了歧管学习方法UMAP。合成和真实数据结果表明，这既简化和改善了多种低维问题，包括密度变化和/或纠缠形状的群集。我们的方法简化了聚类，因为拓扑预处理始终降低DBSCAN的参数灵敏度。然后，用dbscan聚类所得的嵌入可以超过诸如spectacl和clustergan之类的复杂方法。最后，我们的调查表明，聚类中的关键问题似乎不是数据的标称维度或其中包含多少不相关的功能，而是\ textIt {可分离}群集在环境观察空间中的\ textit {可分离}，它们嵌入了它们中。 ，通常是数据特征定义的（高维）欧几里得空间。我们的方法之所以成功，是因为我们将数据投影到更合适的空间后，从某种意义上说，我们执行了群集分析。

邻居Embeddings是一种使用$ k $ nn图来可视化复杂的高维数据集的方法。为了找到低维嵌入，这些算法将相邻对点之间的吸引力与所有点之间的排斥力相结合。这种算法的最受欢迎的例子之一是T-SNE。在这里，我们经验证明使用夸张参数改变T-SNE中的吸引力和排斥力之间的平衡产生了一种嵌入式，其特点是简单的折衷：更强的吸引力可以更好地代表连续的歧管结构，而更强排斥可以更好地代表离散的集群结构，并收益率较高$ K $ NN召回。我们发现Umap Embeddings对应于涉及吸引力的T-SNE;数学分析表明，这是因为UMAP采用的负采样优化策略强烈降低了有效的排斥。同样，Forceatlas2通常用于可视化发育​​单细胞转录组数据，产生与T-SNE相对应的嵌入，吸引力增加更多。在这个频谱的极端Lieglacian eigenmaps。我们的结果表明，许多突出的邻居嵌入算法可以放置在吸引力频谱上，并突出显示它们之间的固有折衷。

We review clustering as an analysis tool and the underlying concepts from an introductory perspective. What is clustering and how can clusterings be realised programmatically? How can data be represented and prepared for a clustering task? And how can clustering results be validated? Connectivity-based versus prototype-based approaches are reflected in the context of several popular methods: single-linkage, spectral embedding, k-means, and Gaussian mixtures are discussed as well as the density-based protocols (H)DBSCAN, Jarvis-Patrick, CommonNN, and density-peaks.

我们提出了TOD，这是一个在分布式多GPU机器上进行有效且可扩展的离群检测（OD）的系统。 TOD背后的一个关键思想是将OD应用程序分解为基本张量代数操作。这种分解使TOD能够通过利用硬件和软件中深度学习基础架构的最新进展来加速OD计算。此外，要在有限内存的现代GPU上部署昂贵的OD算法，我们引入了两种关键技术。首先，可证明的量化可以加快OD计算的速度，并通过以较低的精度执行特定的浮点操作来减少其内存足迹，同时证明没有准确的损失。其次，为了利用多个GPU的汇总计算资源和内存能力，我们引入了自动批处理，该批次将OD计算分解为小批次，以便在多个GPU上并行执行。 TOD支持一套全面且多样化的OD算法，例如LOF，PCA和HBOS以及实用程序功能。对真实和合成OD数据集的广泛评估表明，TOD平均比领先的基于CPU的OD系统PYOD快11.6倍（最大加速度为38.9倍），并且比各种GPU底线要处理的数据集更大。值得注意的是，TOD可以直接整合其他OD算法，并提供了将经典OD算法与深度学习方法相结合的统一框架。这些组合产生了无限数量的OD方法，其中许多方法是新颖的，可以很容易地在TOD中进行原型。