数十年的计算机科学历史一直致力于设计有效存储和检索信息的解决方案。hashmap（或hashtable）是一种流行的信息存储数据结构，因为它们可以保证元素插入和检索的恒定时间。

然而，尽管hashmap很流行，但很少在 GPU 加速计算的背景下进行讨论。虽然 GPU 以其大量线程和计算能力而闻名，但其极高的内存带宽可以加速许多数据结构（例如hashmap）。

这篇文章将介绍哈hashmap的基础知识以及它们的内存访问模式如何使其非常适合 GPU 加速。我们将介绍cuCollections，这是一个用于并发数据结构（包括hashmap）的新开源 CUDA C++ 库。

最后，如果有兴趣在应用程序中使用 GPU 加速的哈希表，我们提供了多列关系连接算法的示例实现case。RAPIDS cuDF 集成了 GPU 哈希表，这有助于为数据科学工作负载实现令人难以置信的加速。要了解更多信息，请参阅GitHub 上的rapidsai/cudf; 以及使用示例case 使用 Dask 和 RAPIDS 加速 TF-IDF 进行自然语言处理。

还可以将 cuCollections 用于表格数据处理之外的许多用例，例如推荐系统、流压缩、图形算法、基因组学和稀疏线性代数运算。请参阅Pinterest 通过切换推荐系统的 GPU 加速将主页订阅参与度提高 16%了解更多信息。

深入研究 LSH 函数的组合以保证更可靠的搜索

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

在本系列文章的最后两部分中，我们深入研究了 LSH —— 一种将输入向量转换为低维散列值，同时保留有关其相似性的信息的算法。特别是，我们已经研究了两种适用于不同距离度量的算法：

相似性搜索，第 5 部分：局部敏感哈希 (LSH): 经典的LSH算法构造反映向量Jaccard系数信息的签名。

相似性搜索，第 6 部分：LSH 森林的随机投影: 随机投影方法构建了保持向量余弦相似性的超平面森林。

事实上，LSH 算法也适用于其他距离度量。尽管每种方法都有其独特的部分，但每种方法中都出现了许多共同的概念和公式。为了促进未来新方法的学习过程，我们将更多地关注理论并提供一些经常出现在高级 LSH 文献中的基本定义和定理。在本文结束时，我们将能够通过简单地将基本方案组合为乐高积木来构建更复杂的 LSH 方案。

最后我们将了解如何将欧几里得距离纳入 LSH 中。

注意：

• 作为主要先决条件，您应该已经熟悉本系列文章的第 5 部分和第 6 部分。如果没有，强烈建议先阅读它们。

• 余弦距离定义在 [0, 2] 范围内。为简单起见，我们将其映射到区间 [0, 1]，其中 0 和 1 分别表示最低和最高可能的相似度。

了解如何对数据进行哈希处理并通过构造随机超平面来反映其相似性

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

在上一部分中，我们研究了 LSH 的主要范例，即将输入向量转换为低维hash值，同时保留有关其相似性的信息。为了获取hash值（签名），使用了 minhash 函数。在本文中，我们将随机投影输入数据以获得类似的二进制向量。

探索如何将相似性信息合并到哈希函数中

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

在本系列文章的前几部分中，我们讨论了倒排文件索引、产品量化和 HNSW 以及如何将它们结合使用来提高搜索质量。在本章中，我们将研究一种主要不同的方法，该方法可以保持高搜索速度和质量。

局部敏感哈希（LSH）是一组方法，用于通过将数据向量转换为哈希值来缩小搜索范围，同时保留有关其相似性的信息。

我们将讨论传统方法，该方法包括三个步骤：

1. Shingling：将原始文本编码为向量。
2. MinHashing ：将向量转换为称为签名的特殊表示，可用于比较它们之间的相似性。
3. LSH函数：将签名块散列到不同的桶中。如果一对向量的签名至少一次落入同一个桶中，则它们被视为候选向量。

我们将在整篇文章中逐步深入探讨每个步骤的细节。

了解如何构建高效的多层图以提高海量数据的搜索速度

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

分层可导航小世界(HNSW) 是一种用于近似搜索最近邻居的最先进算法。在底层，HNSW 构建了优化的图结构，使其与本系列文章前面部分中讨论的其他方法非常不同。

HNSW 的主要思想是构建这样一个图，其中任何一对顶点之间的路径都可以通过少量步骤遍历。

著名的六次握手规则的一个著名类比与此方法有关：

所有人之间的社会关系距离不超过 6 个。

在继续讨论 HNSW 的内部工作之前，让我们首先讨论跳跃列表和可导航小世界——HNSW 实现中使用的关键数据结构。

了解如何结合两个基本的相似性搜索索引以发挥两者的优势

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

在本系列的前两部分中，我们讨论了信息检索中的两种基本算法：倒排文件索引和乘积量化。它们都优化了搜索性能，但侧重于不同的方面：第一个加速了搜索速度，而后者将向量压缩为更小的、节省内存的表示形式。

由于两种算法侧重于不同的方面，自然出现的问题是是否可以将这两种算法合并为一种新算法

在本文中，我们将结合这两种方法的优点来产生快速且内存高效的算法。作为参考，大多数讨论的想法都将基于本文。

在深入研究细节之前，有必要了解残差向量(residual vectors)是什么，并对它们的有用属性有一个简单的直觉。稍后我们将在设计算法时使用它们。

学习有效压缩大数据的强大技术

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

在本系列文章的第一部分中，我们研究了用于执行相似性搜索的 kNN 和倒排文件索引结构。正如我们所知，kNN 是最直接的方法，而倒排文件索引则在其之上发挥作用，建议在速度加速和准确性之间进行权衡。然而，这两种方法都不使用数据压缩技术，这可能会导致内存问题，特别是在数据集较大且 RAM 有限的情况下。在本文中，我们将尝试通过研究另一种称为“乘积量化(Product Quantization)”的方法来解决此问题。