一种提高在线数据库速度的新方法

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

但是，由于传统的哈希函数是随机生成代码的，所以有时会出现两份数据的哈希值相同的情况。这会导致冲突——当搜索一个项目时，用户会指向许多具有相同哈希值的数据。找到正确的需要更长的时间，从而导致搜索速度变慢并降低性能。

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

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

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

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

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

Sabek与电气工程和计算机科学(EECS)研究生KapilVaidya是该论文的共同主要作者。慕尼黑工业大学的研究生多米尼克·霍恩(DominickHorn)加入了他们的合著者行列;AndreasKipf，麻省理工学院博士后;MichaelMitzenmacher，哈佛大学JohnA.Paulson工程与应用科学学院计算机科学教授;资深作者TimKraska，麻省理工学院EECS副教授，数据系统和人工智能实验室联合主任。

散列出来

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

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

“我们想知道，如果我们对数据了解得更多——它来自特定的分布——我们是否可以使用学习模型来构建一个可以真正减少冲突的哈希函数?”维迪亚说。

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

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

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

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

更少的碰撞，更快的结果

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

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

“在子模型的某个阈值处，您可以获得足够的信息来构建哈希函数所需的近似值。但在那之后，它不会导致碰撞减少方面的更多改进，”Sabek说。

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

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

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！