一种提高在线数据库速度的新方法-如何加快数据库查询速度

来自麻省理工学院和其他地方的研究人员开始研究他们是否可以使用机器学习来构建更好的哈希函数

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

然而，由于传统的哈希函数随机生成代码，有时可以使用相同的值对两段数据进行哈希。当搜索一个项目时，这会导致用户指向具有相同哈希值的多条数据时发生冲突。找到正确的搜索需要更长的时间，导致搜索速度变慢，性能降低。

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

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

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

“我们在这项工作中发现，在某些情况下，我们可以在哈希函数的计算和我们将面临的冲突之间找到一个更好的折衷方案。我们可以稍微增加哈希函数的运算时间，但同时我们可以在特定情况下非常显著地减少冲突。”计算机科学与人工智能实验室（CSAIL）麻省理工学院数据系统小组的博士后Ibrahim Sabek说。

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

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

完美的哈希函数提供了一种无冲突的选择。研究人员为该函数提供了一些额外的知识，例如数据要放入的插槽数量。然后，它可以执行额外的计算，以确定将每个密钥放在何处以避免冲突。然而，这些增加的计算使函数更难创建，效率也更低。

Vaidya说：“我们想知道，如果我们对来自特定分布的数据有更多了解，我们是否可以使用学习到的模型来构建一个哈希函数，从而实际减少冲突？”

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

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

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

Ibrahim Sabek解释说：“我们可能有大量的数据输入，每一个输入和下一个输入之间都有不同的差距，所以学习这是非常困难的。”

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

在研究如何使用学习模型进行哈希运算时，研究人员还发现，子模型的数量对整个过程的影响最大。每个学习模型由近似数据分布的较小线性模型组成。有了更多的子模型，学习的模型会产生更精确的近似值，但需要更多的时间。

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

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

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