我已经实现了基于局部聚类系数算法的MapReduce范例。然而，在处理更大的数据集或特定数据集（节点平均度较高）时，我遇到了严重的问题。我尝试调整我的Hadoop平台和代码，但结果令人不满意（至少可以这么说）。现在我将注意力转向实际改变/改进算法。以下是我的当前算法（伪代码）：
foreach(Node in Graph) {
//Job1
/* Transform edge-based input dataset to node-based dataset */
//Job2
map() {
emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours
emit(this.Node, this.Node) //emit myself to myself
}
reduce() {
NodeNeighbourhood nodeNeighbourhood;
while(values.hasNext) {
if(myself)
this.nodeNeighbourhood.setCentralNode(values.next) //store myself data
else
this.nodeNeighbourhood.addNeighbour(values.next) //store neighbour data
}
emit(null, this.nodeNeighbourhood)
}
//Job3
map() {
float lcc = calculateLocalCC(this.nodeNeighbourhood)
emit(0, lcc) //emit all lcc to specific key, combiners are used
}
reduce() {
float combinedLCC;
int numberOfNodes;
while(values.hasNext) {
combinedLCC += values.next;
}
emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient
}
}
关于代码的更多细节，对于有向图，邻居数据仅限于节点ID和OUT边缘目标ID（以减少数据大小），对于无向图，它也是节点ID和边缘目标ID。排序和合并缓冲区增加到1.5 Gb，合并流为80。
可以清楚地看到，Job2是整个算法的实际问题。它生成了大量数据，必须进行排序/复制/合并。这基本上杀死了我的算法性能，特别是对于某些数据集。有人能指导我如何改进算法吗（我考虑创建一个迭代的Job2，每次迭代只“处理” N中的M个节点，直到处理完每个节点，但我已经放弃了这个想法）。我认为Job2的映射输出应该减少，以避免昂贵的排序/合并过程，这会影响性能。
我还为Giraph平台实现了相同的算法（3个作业，相同的“通信”模式，也存在“Job2”问题）。但是，Giraph是一种内存中的平台，对于相同的“有问题”的数据集而言，该算法会出现OutOfMemoryException。
对于任何评论、意见或指南，我将不胜感激。
更新
我将会“彻底”改变算法。我发现了这篇文章：Counting Triangles。
一旦代码实现，我将在此处发布我的意见和更详细的代码（如果这种方法成功的话）。
更新_2
最终，我已经将NodeIterator++算法“修改”以适应我的需求（Yahoo论文可通过文章中的链接获得）。不幸的是，虽然我可以看到性能有所提高，但最终结果并不像我希望的那样好。我得出的结论是，对于这些特定数据集来说，可用于我的集群资源太小，无法使LCC计算成为可能。因此问题仍然存在，或者说它正在发展。有人知道是否存在有效的分布式/顺序算法，可用于计算具有有限资源的LCC或三角形吗？（我并不是说NodeIterator++算法不好，我只是简单地说明我可用的资源不足够）。