研究人員使用機(jī)器學(xué)習(xí)來(lái)構(gòu)建更快、更高效的哈希函數(shù)，這是數(shù)據(jù)庫(kù)的關(guān)鍵組成部分。

哈希是大多數(shù)在線(xiàn)數(shù)據(jù)庫(kù)的核心操作，例如圖書(shū)館目錄或電子商務(wù)網(wǎng)站。哈希函數(shù)生成替換數(shù)據(jù)輸入的代碼。由于這些代碼比實(shí)際數(shù)據(jù)短，而且通常是固定長(zhǎng)度，因此更容易查找和檢索原始信息。

但是，由于傳統(tǒng)的哈希函數(shù)是隨機(jī)生成代碼的，所以有時(shí)會(huì)出現(xiàn)兩份數(shù)據(jù)的哈希值相同的情況。這會(huì)導(dǎo)致沖突——當(dāng)搜索一個(gè)項(xiàng)目時(shí)，用戶(hù)會(huì)指向許多具有相同哈希值的數(shù)據(jù)。找到正確的需要更長(zhǎng)的時(shí)間，從而導(dǎo)致搜索速度變慢并降低性能。

某些類(lèi)型的哈希函數(shù)（稱(chēng)為完美哈希函數(shù)）旨在以防止沖突的方式對(duì)數(shù)據(jù)進(jìn)行排序。但它們必須為每個(gè)數(shù)據(jù)集專(zhuān)門(mén)構(gòu)建，并且比傳統(tǒng)的哈希函數(shù)需要更多的時(shí)間來(lái)計(jì)算。

由于散列在如此多的應(yīng)用程序中使用，從數(shù)據(jù)庫(kù)索引到數(shù)據(jù)壓縮再到密碼學(xué)，快速高效的散列函數(shù)至關(guān)重要。因此，麻省理工學(xué)院和其他地方的研究人員著手研究他們是否可以使用機(jī)器學(xué)習(xí)來(lái)構(gòu)建更好的哈希函數(shù)。

他們發(fā)現(xiàn)，在某些情況下，使用學(xué)習(xí)模型而不是傳統(tǒng)的哈希函數(shù)可能會(huì)導(dǎo)致一半的沖突。學(xué)習(xí)模型是通過(guò)在數(shù)據(jù)集上運(yùn)行機(jī)器學(xué)習(xí)算法而創(chuàng)建的模型。他們的實(shí)驗(yàn)還表明，學(xué)習(xí)模型通常比完美的哈希函數(shù)計(jì)算效率更高。

“我們?cè)谶@項(xiàng)工作中發(fā)現(xiàn)，在某些情況下，我們可以在哈希函數(shù)的計(jì)算和我們將面臨的沖突之間做出更好的權(quán)衡。我們可以稍微增加哈希函數(shù)的計(jì)算時(shí)間，但同時(shí)我們可以在某些情況下顯著減少?zèng)_突，”麻省理工學(xué)院計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室數(shù)據(jù)系統(tǒng)組的博士后 Ibrahim Sabek 說(shuō)（中國(guó)航空航天局）。

他們的研究將在超大型數(shù)據(jù)庫(kù)國(guó)際會(huì)議上展示，展示了如何設(shè)計(jì)哈希函數(shù)來(lái)顯著加快大型數(shù)據(jù)庫(kù)中的搜索速度。例如，他們的技術(shù)可以加速科學(xué)家用來(lái)存儲(chǔ)和分析 DNA、氨基酸序列或其他生物信息的計(jì)算系統(tǒng)。

Sabek與電氣工程和計(jì)算機(jī)科學(xué) (EECS) 研究生 Kapil Vaidya是該論文的共同主要作者。慕尼黑工業(yè)大學(xué)的研究生多米尼克·霍恩 (Dominick Horn) 加入了他們的合著者行列；Andreas Kipf，麻省理工學(xué)院博士后；Michael Mitzenmacher，哈佛大學(xué) John A. Paulson 工程與應(yīng)用科學(xué)學(xué)院計(jì)算機(jī)科學(xué)教授；作者 Tim Kraska，麻省理工學(xué)院 EECS 副教授，數(shù)據(jù)系統(tǒng)和人工智能實(shí)驗(yàn)室聯(lián)合主任。

散列出來(lái)

給定一個(gè)數(shù)據(jù)輸入或密鑰，傳統(tǒng)的哈希函數(shù)會(huì)生成一個(gè)隨機(jī)數(shù)或代碼，它對(duì)應(yīng)于將存儲(chǔ)該密鑰的插槽。舉一個(gè)簡(jiǎn)單的例子，如果有 10 個(gè)鍵被放入 10 個(gè)槽中，該函數(shù)將為每個(gè)輸入生成一個(gè) 1 到 10 之間的隨機(jī)整數(shù)。兩個(gè)密鑰很可能終會(huì)出現(xiàn)在同一個(gè)插槽中，從而導(dǎo)致沖突。

完美的哈希函數(shù)提供了一種無(wú)沖突的替代方案。研究人員為該函數(shù)提供了一些額外的知識(shí)，例如數(shù)據(jù)要放入的槽的數(shù)量。然后它可以執(zhí)行額外的計(jì)算以確定將每個(gè)鍵放在哪里以避免沖突。然而，這些增加的計(jì)算使得函數(shù)更難創(chuàng)建且效率更低。

“我們想知道，如果我們對(duì)數(shù)據(jù)了解更多——它會(huì)來(lái)自特定的分布——我們是否可以使用學(xué)習(xí)模型來(lái)構(gòu)建一個(gè)可以真正減少?zèng)_突的哈希函數(shù)？” 維迪亞說(shuō)。

數(shù)據(jù)分布顯示數(shù)據(jù)集中所有可能的值，以及每個(gè)值出現(xiàn)的頻率。該分布可用于計(jì)算特定值在數(shù)據(jù)樣本中的概率。

研究人員從數(shù)據(jù)集中提取了一個(gè)小樣本，并使用機(jī)器學(xué)習(xí)來(lái)近似數(shù)據(jù)分布的形狀，或者數(shù)據(jù)的分布方式。然后，學(xué)習(xí)的模型使用近似值來(lái)預(yù)測(cè)數(shù)據(jù)集中鍵的位置。

他們發(fā)現(xiàn)，與完美的哈希函數(shù)相比，學(xué)習(xí)模型更容易構(gòu)建且運(yùn)行速度更快，并且如果數(shù)據(jù)以可預(yù)測(cè)的方式分布，則與傳統(tǒng)哈希函數(shù)相比，它們導(dǎo)致的沖突更少。但是，如果數(shù)據(jù)的分布不是可預(yù)測(cè)的，因?yàn)閿?shù)據(jù)點(diǎn)之間的差距變化太大，使用學(xué)習(xí)模型可能會(huì)導(dǎo)致更多的沖突。

“我們可能有大量的數(shù)據(jù)輸入，每一個(gè)與下一個(gè)之間都有不同的差距，因此學(xué)習(xí)這一點(diǎn)非常困難，”Sabek 解釋道。

更少的碰撞，更快的結(jié)果

當(dāng)數(shù)據(jù)以可預(yù)測(cè)的方式分布時(shí)，與傳統(tǒng)的哈希函數(shù)相比，學(xué)習(xí)模型可以將數(shù)據(jù)集中鍵沖突的比例從 30% 降低到 15%。他們還能夠?qū)崿F(xiàn)比完美哈希函數(shù)更好的吞吐量。在的情況下，學(xué)習(xí)模型將運(yùn)行時(shí)間減少了近 30%。

當(dāng)他們探索使用學(xué)習(xí)模型進(jìn)行哈希處理時(shí)，研究人員還發(fā)現(xiàn)，吞吐量受子模型數(shù)量的影響。每個(gè)學(xué)習(xí)模型都由更小的線(xiàn)性模型組成，這些模型近似于數(shù)據(jù)分布。有了更多的子模型，學(xué)習(xí)到的模型會(huì)產(chǎn)生更準(zhǔn)確的近似值，但需要更多的時(shí)間。

“在子模型的某個(gè)閾值處，您可以獲得足夠的信息來(lái)構(gòu)建哈希函數(shù)所需的近似值。但在那之后，它不會(huì)在減少碰撞方面帶來(lái)更多改進(jìn)，”Sabek 說(shuō)。

在這種分析的基礎(chǔ)上，研究人員希望使用學(xué)習(xí)模型為其他類(lèi)型的數(shù)據(jù)設(shè)計(jì)哈希函數(shù)。他們還計(jì)劃探索可以插入或刪除數(shù)據(jù)的數(shù)據(jù)庫(kù)的學(xué)習(xí)哈希。當(dāng)數(shù)據(jù)以這種方式更新時(shí)，模型需要相應(yīng)地改變，但是在保持準(zhǔn)確性的同時(shí)改變模型是一個(gè)難題。

“我們希望鼓勵(lì)社區(qū)在更基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和操作中使用機(jī)器學(xué)習(xí)。任何一種核心數(shù)據(jù)結(jié)構(gòu)都為我們提供了使用機(jī)器學(xué)習(xí)捕獲數(shù)據(jù)屬性并獲得更好性能的機(jī)會(huì)。我們還有很多可以探索的地方，”Sabek 說(shuō)。

這項(xiàng)工作部分得到了谷歌、英特爾、微軟、科學(xué)基金會(huì)、美國(guó)空軍研究實(shí)驗(yàn)室和美國(guó)空軍人工智能加速器的支持。