使用MapReduce編程模型比較兩個大型數據集

-1

比方說，我有兩個相當大的數據集 - 第一個叫做「Base」，它包含2億個製表符分隔的行，第二個調用「MatchSet」，它有1000萬個標籤分隔的相似數據行。讓我們假設我也有一個稱爲Match（row1，row2）的任意函數，Match（）基本上包含了一些針對row1（來自MatchSet）的啓發式算法，並將它與row2（來自Base）進行比較，並確定它們是否是在某些方面類似。使用MapReduce編程模型比較兩個大型數據集

比方說，在Match（）中實現的規則是自定義和複雜規則，並非簡單的字符串匹配，涉及一些專有方法。現在我們假設Match（row1，row2）是用僞代碼編寫的，所以在另一種語言中的實現不是問題（儘管它今天是在C++中）。

在一個線性模型中，aka程序運行在一個巨大的處理器上 - 我們將從MatchSet中讀取每一行，並從Base中讀取每行，並使用Match（）比較另一行，並寫出我們的匹配統計數據。例如，我們可能會捕獲：MatchSet的X記錄是強匹配，MatchSet的Y記錄是弱匹配，MatchSet的Z記錄不匹配。我們還會編寫強/弱/非值來分隔文件以供檢查。阿卡，各種各樣的嵌套循環：

for each row1 in MatchSet 
{ 
    for each row2 in Base 
    { 
     var type = Match(row1,row2); 
     switch(type) 
     { 
      //do something based on type 
     } 
    } 
}

我已經開始考慮的Hadoop流爲運行這些比較在很短的時間量批作業的方法。不過，我在爲這類問題尋找map-reduce範例時遇到了一些困難。

我在這一點上非常清楚地知道如何從hadoop中獲取單個輸入，使用映射函數來關閉數據，然後發出結果以減少。然而，比較兩組記錄的「嵌套循環」方法與我有點混淆。

最接近我的解決方案是，我基本上仍然需要在2億條記錄中並行執行1000萬條記錄比較，因此每個節點有200萬/ n個節點* 1000萬次迭代。那是最有效的方法嗎？

來源

2011-11-28 j03m

我投下了這個問題。首先它不能太啓發，因爲我們仍然每次看1條記錄（至少在上面的描述中）。那麼這個問題似乎更多的是理解map-reduce過程，然後調用算法。然後啓發式部分實際上是一個算法，這裏沒有描述。所以可能這個問題應該被重寫。 – mariotti

這是肯定的，這是5年前，這可能是真的。我沒有編輯（因爲我實際上不再關心），我似乎無法刪除。 – j03m

檢查論文'Data-Intensive Text Processing with MapReduce'中的Section 3.5 - Relational Joins。我沒有詳細介紹，但它可能會幫助你。

來源

2011-11-28 16:07:15

這是一篇有趣的論文 - 但這裏的加入都是基於某個共享密鑰的。如果你考慮我的問題，我沒有那麼奢侈。 – j03m

它在我的閱讀列表中。但是，我認爲你會覺得很有趣。 –

從您的描述來看，您覺得您的問題可能非常複雜，可能是curse of dimensionality的受害者。想象一下，例如，你的行表示n維向量，並且基於基向量和MatchSet向量之間的歐幾里得距離，匹配函數是「強」，「弱」或「不匹配」。在速度，記憶和近似答案的質量之間進行權衡，有很多技術可以解決這些問題。關鍵的是，這些技術通常具有已知的時間和空間界限，以及在給定的MatchSet原型周圍的某個距離內找到一個點的概率，所有這些取決於算法的一些參數。

，而不是我在這裏絮叨的話，請考慮閱讀以下事項：

Locality Sensitive Hashing
當你搜索「局部性敏感哈希映射精簡」在谷歌學術搜索的前幾個命中。特別是，我記得閱讀[Das，Abhinandan S.等人。「Google新聞個性化：可擴展的在線協作過濾。」第16屆萬維網國際會議論文集。ACM，2007]感興趣。現在

，在另一方面，如果你可以設計一個方案是直接服從於某種形式的散列的，那麼你可以很容易地產生了這樣一個散列每個記錄的鍵（或者甚至是一小部分可能散列鍵，其中之一將匹配查詢「基本」數據），並且問題變成一個簡單的大（ - ）規模連接。（我說「很大」，因爲如果問題確實是連接，那麼連接10M行的200M行是相當小的）。作爲例子，考慮CDDB計算任何音樂CD的32位ID的方式CDDB1 calculation。有時，給定的標題可能會產生稍微不同的ID（即相同標題的不同CD，甚至相同的CD讀幾次）。但總體而言，該標題有一小組不同的ID。以MatchSet的小型複製爲代價，在這種情況下，您可以獲得非常快速的搜索結果。

來源

2013-04-10 04:47:03

這是一個古老的問題，但假設您的單流作業執行200M * 10M Match（）計算，您提出的解決方案是正確的。通過進行N批（200M/N）* 10M計算，您已經實現了N倍加速。通過在地圖階段進行計算，然後進行閾值處理並將結果轉向強/弱/無匹配縮減器，您可以收集輸出結果以分離文件。

如果可以使用其他優化，他們想要應用於單流和並行版本。示例包括阻塞，以便您需要執行少於200M * 10M的計算或預計算10M匹配集的算法常量部分。

來源

2013-09-16 16:19:25

使用MapReduce編程模型比較兩個大型數據集

回答

相關問題