新方法加速了大型数据库中的数据检索
研究人员利用机器学习构建了更快、更高效的哈希函数，这是数据库的关键组成部分
哈希是大多数在线数据库的核心操作，例如图书馆目录或电子商务网站。哈希函数生成代码，直接确定数据存储的位置。因此，使用这些代码可以更轻松地查找和检索数据。
然而，由于传统哈希函数随机生成代码，有时两个数据片段可以使用相同的值进行哈希。这会导致冲突–当搜索一个项目指向具有相同哈希值的许多数据片段时。找到正确的数据需要更长的时间，导致搜索变慢且性能降低。
某些类型的哈希函数，称为完美哈希函数，旨在以防止冲突的方式放置数据。但是，为每个数据集构建它们需要耗费大量时间，并且比传统哈希函数需要更多的计算时间。
由于哈希在许多应用程序中使用，从数据库索引到数据压缩到加密，因此快速高效的哈希函数至关重要。因此，来自MIT和其他地方的研究人员开始研究是否可以使用机器学习来构建更好的哈希函数。
他们发现，在某些情况下，使用学习模型而不是传统哈希函数可以减少一半的冲突。这些学习模型是通过在数据集上运行机器学习算法以捕获特定特征来创建的。该团队的实验还表明，学习模型通常比完美哈希函数更具计算效率。
“我们在这项工作中发现，在某些情况下，我们可以在哈希函数的计算和我们将面临的冲突之间取得更好的权衡。在这些情况下，哈希函数的计算时间可能会稍微增加，但同时它的冲突可以显着减少，”计算机科学和人工智能实验室（CSAIL）MIT数据系统组的博士后Ibrahim Sabek说。
他们的研究将在2023年的国际大型数据库会议上展示，展示了如何设计哈希函数以显着加快在巨大数据库中的搜索速度。例如，他们的技术可以加速科学家用于存储和分析DNA，氨基酸序列或其他生物信息的计算系统。
Sabek是与电气工程和计算机科学（EECS）研究生Kapil Vaidya共同撰写论文的合作者。他们的合作者是技术大学慕尼黑的研究生Dominik Horn，MIT博士后Andreas Kipf，哈佛约翰·A·保罗森工程与应用科学学院计算机科学教授Michael Mitzenmacher和MIT的EECS副教授、数据、系统和AI实验室联合主任Tim Kraska。
哈希化
给定数据输入或键，传统哈希函数会生成一个随机数或代码，该代码对应于存储该键的插槽。以一个简单的例子来说，如果有10个键要放入10个插槽中，该函数会为每个输入生成介于1和10之间的整数。很可能会发生两个键最终进入同一个插槽的情况，从而导致冲突。
完美哈希函数提供了一种无冲突的替代方法。研究人员为函数提供了一些额外的知识，例如数据要放置的插槽数量。然后，它可以执行其他计算以确定在避免冲突的情况下放置每个键的位置。但是，这些添加的计算使函数更难创建且效率更低。
“我们想知道，如果我们对数据了解更多–它将来自特定分布–我们是否可以使用学习模型来构建可以实际减少冲突的哈希函数？”Vaidya说。
数据分布显示数据集中所有可能的值以及每个值出现的频率。分布可以用于计算特定值在数据样本中的概率。
研究人员从数据集中取出了一个小样本，并使用机器学习来近似数据分布的形状或数据分布的展开方式。然后，学习模型使用近似值来预测数据集中键的位置。
他们发现，如果数据以可预测的方式分布，学习模型比完美哈希函数更容易构建和更快运行，同时会导致比传统哈希函数更少的冲突。但是，如果数据不可预测分布，因为数据点之间的间隔变化太大，使用学习模型可能会导致更多的冲突。
“我们可能有大量的数据输入，而连续输入之间的间隔非常不同，因此学习一个模型来捕捉这些输入的数据分布是相当困难的，”Sabek解释道。
碰撞更少，结果更快
当数据可预测地分布时，与传统哈希函数相比，学习模型可以将数据集中碰撞键的比率从30％降至15％。它们还能够实现比完美哈希函数更好的吞吐量。在最佳情况下，学习模型将运行时间缩短了近30％。
在探索学习模型用于哈希时，研究人员还发现吞吐量受子模型数量影响最大。每个学习模型由小型线性模型组成，这些模型逼近不同部分数据的数据分布。使用更多的子模型，学习模型可以产生更准确的逼近，但需要更多时间。
“在子模型达到一定阈值时，您会获得足够的信息来构建哈希函数所需的逼近。但在那之后，它不会导致碰撞降低的更多改进，”Sabek说。
在此分析的基础上，研究人员希望使用学习模型为其他类型的数据设计哈希函数。他们还计划探索用于可以插入或删除数据的数据库的学习哈希。当以这种方式更新数据时，模型需要相应地更改，但是在保持准确性的同时更改模型是一个困难的问题。
“我们希望鼓励社区在更基本的数据结构和算法中使用机器学习。任何类型的核心数据结构都为我们提供了使用机器学习捕获数据属性和获得更好性能的机会。我们仍然有很多可以探索的地方，”Sabek说。
“哈希和索引函数是许多数据库功能的核心。鉴于用户和用例的多样性，没有一种大小适合所有哈希函数，而学习模型有助于使数据库适应特定用户。这篇论文很好地平衡了这些新技术的可行性分析，并且在严格讨论优缺点方面做得很好，有助于我们建立对这些方法什么情况下可以有效运行的理解，”亚马逊的主要机器学习科学家Murali Narayanaswamy说。他没有参与这项工作。“探索这些增强功能是学术界和工业界的一个令人兴奋的研究领域，这项工作所展现出来的严谨性对于这些方法产生广泛影响至关重要。”
本研究得到了Google、英特尔、微软、美国国家科学基金会、美国空军研究实验室和美国空军人工智能加速器的部分支持。
