麻省理工學(xué)院:一種提高在線數(shù)據(jù)庫速度的新方法
研究人員使用機器學(xué)習(xí)來構(gòu)建更快、更高效的哈希函數(shù)，這是數(shù)據(jù)庫的關(guān)鍵組成部分。
哈希是大多數(shù)在線數(shù)據(jù)庫的核心操作，例如圖書館目錄或電子商務(wù)網(wǎng)站。哈希函數(shù)生成替換數(shù)據(jù)輸入的代碼。由于這些代碼比實際數(shù)據(jù)短，而且通常是固定長度，因此更容易查找和檢索原始信息。
但是，由于傳統(tǒng)的哈希函數(shù)是隨機生成代碼的，所以有時會出現(xiàn)兩份數(shù)據(jù)的哈希值相同的情況。這會導(dǎo)致沖突——當(dāng)搜索一個項目時，用戶會指向許多具有相同哈希值的數(shù)據(jù)。找到正確的需要更長的時間，從而導(dǎo)致搜索速度變慢并降低性能。
某些類型的哈希函數(shù)（稱為完美哈希函數(shù)）旨在以防止沖突的方式對數(shù)據(jù)進行排序。但它們必須為每個數(shù)據(jù)集專門構(gòu)建，并且比傳統(tǒng)的哈希函數(shù)需要更多的時間來計算。
由于散列在如此多的應(yīng)用程序中使用，從數(shù)據(jù)庫索引到數(shù)據(jù)壓縮再到密碼學(xué)，快速高效的散列函數(shù)至關(guān)重要。因此，麻省理工學(xué)院和其他地方的研究人員著手研究他們是否可以使用機器學(xué)習(xí)來構(gòu)建更好的哈希函數(shù)。
他們發(fā)現(xiàn)，在某些情況下，使用學(xué)習(xí)模型而不是傳統(tǒng)的哈希函數(shù)可能會導(dǎo)致一半的沖突。學(xué)習(xí)模型是通過在數(shù)據(jù)集上運行機器學(xué)習(xí)算法而創(chuàng)建的模型。他們的實驗還表明，學(xué)習(xí)模型通常比完美的哈希函數(shù)計算效率更高。
“我們在這項工作中發(fā)現(xiàn)，在某些情況下，我們可以在哈希函數(shù)的計算和我們將面臨的沖突之間做出更好的權(quán)衡。我們可以稍微增加哈希函數(shù)的計算時間，但同時我們可以在某些情況下顯著減少沖突，”麻省理工學(xué)院計算機科學(xué)與人工智能實驗室數(shù)據(jù)系統(tǒng)組的博士后 Ibrahim Sabek 說（中國航空航天局）。
他們的研究將在超大型數(shù)據(jù)庫國際會議上展示，展示了如何設(shè)計哈希函數(shù)來顯著加快大型數(shù)據(jù)庫中的搜索速度。例如，他們的技術(shù)可以加速科學(xué)家用來存儲和分析 DNA、氨基酸序列或其他生物信息的計算系統(tǒng)。
Sabek與電氣工程和計算機科學(xué) (EECS) 研究生 Kapil Vaidya是該論文的共同主要作者。慕尼黑工業(yè)大學(xué)的研究生多米尼克·霍恩 (Dominick Horn) 加入了他們的合著者行列；Andreas Kipf，麻省理工學(xué)院博士后；Michael Mitzenmacher，哈佛大學(xué) John A. Paulson 工程與應(yīng)用科學(xué)學(xué)院計算機科學(xué)教授；作者 Tim Kraska，麻省理工學(xué)院 EECS 副教授，數(shù)據(jù)系統(tǒng)和人工智能實驗室聯(lián)合主任。
散列出來
給定一個數(shù)據(jù)輸入或密鑰，傳統(tǒng)的哈希函數(shù)會生成一個隨機數(shù)或代碼，它對應(yīng)于將存儲該密鑰的插槽。舉一個簡單的例子，如果有 10 個鍵被放入 10 個槽中，該函數(shù)將為每個輸入生成一個 1 到 10 之間的隨機整數(shù)。兩個密鑰很可能終會出現(xiàn)在同一個插槽中，從而導(dǎo)致沖突。
完美的哈希函數(shù)提供了一種無沖突的替代方案。研究人員為該函數(shù)提供了一些額外的知識，例如數(shù)據(jù)要放入的槽的數(shù)量。然后它可以執(zhí)行額外的計算以確定將每個鍵放在哪里以避免沖突。然而，這些增加的計算使得函數(shù)更難創(chuàng)建且效率更低。
“我們想知道，如果我們對數(shù)據(jù)了解更多——它會來自特定的分布——我們是否可以使用學(xué)習(xí)模型來構(gòu)建一個可以真正減少沖突的哈希函數(shù)？” 維迪亞說。
數(shù)據(jù)分布顯示數(shù)據(jù)集中所有可能的值，以及每個值出現(xiàn)的頻率。該分布可用于計算特定值在數(shù)據(jù)樣本中的概率。
研究人員從數(shù)據(jù)集中提取了一個小樣本，并使用機器學(xué)習(xí)來近似數(shù)據(jù)分布的形狀，或者數(shù)據(jù)的分布方式。然后，學(xué)習(xí)的模型使用近似值來預(yù)測數(shù)據(jù)集中鍵的位置。
他們發(fā)現(xiàn)，與完美的哈希函數(shù)相比，學(xué)習(xí)模型更容易構(gòu)建且運行速度更快，并且如果數(shù)據(jù)以可預(yù)測的方式分布，則與傳統(tǒng)哈希函數(shù)相比，它們導(dǎo)致的沖突更少。但是，如果數(shù)據(jù)的分布不是可預(yù)測的，因為數(shù)據(jù)點之間的差距變化太大，使用學(xué)習(xí)模型可能會導(dǎo)致更多的沖突。
“我們可能有大量的數(shù)據(jù)輸入，每一個與下一個之間都有不同的差距，因此學(xué)習(xí)這一點非常困難，”Sabek 解釋道。
更少的碰撞，更快的結(jié)果
當(dāng)數(shù)據(jù)以可預(yù)測的方式分布時，與傳統(tǒng)的哈希函數(shù)相比，學(xué)習(xí)模型可以將數(shù)據(jù)集中鍵沖突的比例從 30% 降低到 15%。他們還能夠?qū)崿F(xiàn)比完美哈希函數(shù)更好的吞吐量。在的情況下，學(xué)習(xí)模型將運行時間減少了近 30%。
當(dāng)他們探索使用學(xué)習(xí)模型進行哈希處理時，研究人員還發(fā)現(xiàn)，吞吐量受子模型數(shù)量的影響。每個學(xué)習(xí)模型都由更小的線性模型組成，這些模型近似于數(shù)據(jù)分布。有了更多的子模型，學(xué)習(xí)到的模型會產(chǎn)生更準(zhǔn)確的近似值，但需要更多的時間。
“在子模型的某個閾值處，您可以獲得足夠的信息來構(gòu)建哈希函數(shù)所需的近似值。但在那之后，它不會在減少碰撞方面帶來更多改進，”Sabek 說。
在這種分析的基礎(chǔ)上，研究人員希望使用學(xué)習(xí)模型為其他類型的數(shù)據(jù)設(shè)計哈希函數(shù)。他們還計劃探索可以插入或刪除數(shù)據(jù)的數(shù)據(jù)庫的學(xué)習(xí)哈希。當(dāng)數(shù)據(jù)以這種方式更新時，模型需要相應(yīng)地改變，但是在保持準(zhǔn)確性的同時改變模型是一個難題。
“我們希望鼓勵社區(qū)在更基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和操作中使用機器學(xué)習(xí)。任何一種核心數(shù)據(jù)結(jié)構(gòu)都為我們提供了使用機器學(xué)習(xí)捕獲數(shù)據(jù)屬性并獲得更好性能的機會。我們還有很多可以探索的地方，”Sabek 說。
這項工作部分得到了谷歌、英特爾、微軟、科學(xué)基金會、美國空軍研究實驗室和美國空軍人工智能加速器的支持。
