分組收集與閾值過濾

Question

我想要拿出一個算法來在地圖縮減中執行以下操作。我收到一堆對象和所有者的用戶ID。換句話說，我收到了一堆對：

(object, uid) 

我想對(object,count)的列表，其中count是指在列表中出現的物體的次數就結了。需要說明的是，我們需要如下過濾一切：

1. 我們應該只包含對象對，這樣的對象被重複至少n不同的UID。

2. 我們應該只包含這樣的對象，使得它重複的總次數至少爲m。

對象和用戶都表示爲整數。問題在於將每個(object,uid)對轉換爲(object, 1)然後再通過求和第二個整數來減少它們是很簡單的。然後我可以過濾所有沒有達到（2）閾值的東西。然而，在這一點上，我會失去必要的信息來過濾（1），這是我不知道如何納入這一點。任何人有任何建議？

Answer 1

最簡單也是最自然的方法是依次運行兩個MR作業。第一份工作的目標是統計每個uid擁有每個object多少次。結果是三元組（object，uid,count）。 uid這裏的字段僅用於調試目的 - 在第二份工作中不需要。第二個工作組由object三胞胎。在每年年底減少（）調用，你知道：

1. 爲對象數量的不同uid S的（接待人數三胞胎）
2. 是多少時間object資（count場的總和）總數

所以，現在你可以應用這兩個過濾器。

---

單作業設置也是可以的，但它需要工作在低一點的水平操縱與setSortComparatorClass()，setGroupingComparatorClass()和setPartitionerClass()。想法是，地圖（）應該發射同時包含object和uid字段組合鍵，值不是在所有（NullWritable）用於：僅

1. 分區程序類的分區鍵通過使用該密鑰的object字段。這保證了所有具有相同object的記錄都將轉到相同的reduce任務。
2. SortComparator類的實現方式是首先比較object字段，如果它們相同，則uid字段。
3. GroupingComparatorClass只使用object字段進行比較。

在結果中，單輸入reduce任務將類似於如下：

object1 uid1 
object1 uid2 
object1 uid2 
object1 uid2 
object1 uid5 
object1 uid6 
object1 uid6 
------------ <- boundary of call to reduce 
object7 uid1 
object7 uid1 
object7 uid5 
------------- <-- boundary of call to reduce() 
object9 uid3 

正如你所看到的，UID將被嚴格有序的每次通話中，以減少（），它允許你算兩同時有不同的和不同的用戶的數量。