大家好，我是编程小6，很高兴遇见你，有问题可以及时留言哦。

研究人员使用机器学习来构建更快、更高效的哈希函数，这是数据库的关键组成部分。

哈希是大多数在线数据库（如图书馆目录或电子商务网站）的核心操作。哈希函数生成替换数据输入的代码。由于这些代码比实际数据短，并且通常是固定长度，因此更容易查找和检索原始信息。

但是，由于传统的哈希函数随机生成代码，因此有时可以使用相同的值对两条数据进行哈希处理。这会导致冲突 — 当搜索一个项目时，将用户指向具有相同哈希值的多个数据片段。找到合适的需要更长的时间，从而导致搜索速度变慢和性能降低。

某些类型的哈希函数（称为完美哈希函数）旨在以防止冲突的方式对数据进行排序。但它们必须为每个数据集专门构建，并且比传统的哈希函数需要更多的时间来计算。

由于散列用于许多应用程序，从数据库索引到数据压缩再到加密，因此快速高效的散列函数至关重要。因此，来自麻省理工学院和其他地方的研究人员开始研究他们是否可以使用机器学习来构建更好的哈希函数。

他们发现，在某些情况下，使用学习模型而不是传统的哈希函数可能会导致一半的碰撞。学习模型是通过在数据集上运行机器学习算法创建的模型。他们的实验还表明，学习模型通常比完美的哈希函数更具计算效率。

“我们在这项工作中发现，在某些情况下，我们可以在哈希函数的计算和我们将面临的碰撞之间提出更好的权衡。我们可以稍微增加哈希函数的计算时间，但同时我们可以在某些情况下显着减少碰撞，“计算机科学与人工智能实验室（CSAIL）麻省理工学院数据系统小组的博士后Ibrahim Sabek说。

他们的研究将在超大型数据库国际会议上发表，展示了如何设计哈希函数来显着加快大型数据库中的搜索速度。例如，他们的技术可以加速科学家用来存储和分析DNA，氨基酸序列或其他生物信息的计算系统。

Sabek是该论文与电气工程和计算机科学（EECS）研究生Kapil Vaidya的共同主要作者。共同作者、慕尼黑工业大学研究生多米尼克·霍恩（Dominick Horn）也加入了他们的行列;安德烈亚斯·基普夫，麻省理工学院博士后;迈克尔·米岑马赫，哈佛大学约翰·A·保尔森工程与应用科学学院计算机科学教授;资深作者蒂姆·克拉斯卡（Tim Kraska），麻省理工学院EECS副教授，数据系统和人工智能实验室联合主任。

散列

给定数据输入或密钥，传统的哈希函数会生成一个随机数或代码，该数字或代码对应于将存储该密钥的插槽。举一个简单的例子，如果有 10 个键要放入 10 个插槽，该函数将为每个输入生成一个介于 1 和 10 之间的随机整数。两个密钥极有可能最终位于同一个插槽中，从而导致冲突。

完美的哈希函数提供了一种无冲突的替代方案。研究人员为该功能提供了一些额外的知识，例如数据要放入的插槽数量。然后，它可以执行额外的计算，以确定将每个密钥放在哪里以避免冲突。但是，这些添加的计算使函数更难创建且效率降低。

“我们想知道，如果我们更多地了解数据 - 它将来自特定的分布 - 我们是否可以使用学习模型来构建一个实际上可以减少冲突的哈希函数？”瓦迪亚说。

数据分布显示数据集中所有可能的值，以及每个值出现的频率。分布可用于计算特定值在数据样本中的概率。

研究人员从数据集中抽取了一小部分样本，并使用机器学习来近似数据分布的形状，或者数据是如何分布的。然后，学习的模型使用近似值来预测数据集中键的位置。

他们发现，学习模型比完美的哈希函数更容易构建，运行速度更快，如果数据以可预测的方式分布，它们比传统的哈希函数导致更少的碰撞。但是，如果数据不是可预测的分布，并且由于数据点之间的差距差异太大，则使用学习模型可能会导致更多冲突。

“我们可能有大量的数据输入，每个数据输入与下一个数据输入之间都有不同的差距，因此学习这是相当困难的，”Sabek解释说。

碰撞更少，结果更快

当数据可预测地分布时，与传统的哈希函数相比，学习的模型可以将数据集中冲突键的比例从 30% 降低到 15%。他们还能够实现比完美哈希函数更好的吞吐量。在最好的情况下，学习模型将运行时间缩短了近 30%。

当他们探索使用学习模型进行哈希处理时，研究人员还发现，子模型的数量对整个模型的影响最大。每个学习的模型都由较小的线性模型组成，这些模型近似于数据分布。使用更多的子模型，学习的模型会产生更准确的近似值，但需要更多时间。

“在子模型的某个阈值下，你会得到足够的信息来构建哈希函数所需的近似值。但在那之后，它不会在减少碰撞方面带来更多改进，“萨贝克说。

基于这种分析，研究人员希望使用学习模型为其他类型的数据设计哈希函数。他们还计划探索可以插入或删除数据的数据库的学习哈希。当数据以这种方式更新时，模型需要相应地更改，但是在保持准确性的同时更改模型是一个难题。

“我们希望鼓励社区在更基本的数据结构和操作中使用机器学习。任何类型的核心数据结构都为我们提供了使用机器学习来捕获数据属性并获得更好性能的机会。我们还有很多可以探索的地方，“萨贝克说。

这项工作得到了谷歌、英特尔、微软、国家科学基金会、美国空军研究实验室和美国空军人工智能加速器的部分支持。

#人工智能##机器学习##大数据#