Tôi đã triển khai thực hiện mô hình MapReduce dựa trên local clustering coefficient algorithm. Tuy nhiên tôi đã gặp rắc rối nghiêm trọng đối với các tập dữ liệu lớn hơn hoặc các tập dữ liệu cụ thể (mức độ trung bình cao của một nút). Tôi đã cố gắng để điều chỉnh nền tảng hadoop của tôi và mã tuy nhiên kết quả là không đạt yêu cầu (để nói rằng ít nhất). Không, tôi đã chuyển sự chú ý của mình sang thực sự thay đổi/cải thiện thuật toán. Dưới đây là thuật toán hiện tại của tôi (mã giả)Thuật toán hệ số phân cụm cục bộ phân tán (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
}
}
Ít chi tiết hơn về mã. Đối với đồ thị được chỉ dẫn, dữ liệu lân cận bị giới hạn ở ID đích và ID đích của cạnh ID (để giảm kích thước dữ liệu), đối với các ID đích và ID đích của nút không bị định hướng. Sắp xếp và Hợp nhất bộ đệm được tăng lên 1,5 Gb, hợp nhất các luồng 80.
Có thể thấy rõ rằng Job2 là vấn đề thực tế của toàn bộ thuật toán. Nó tạo ra lượng lớn dữ liệu phải được sắp xếp/sao chép/hợp nhất. Điều này về cơ bản giết hiệu suất thuật toán của tôi đối với các tập dữ liệu nhất định. Ai đó có thể hướng dẫn tôi cách cải thiện thuật toán (tôi đã nghĩ đến việc tạo một Job2 lặp đi lặp lại ["process" chỉ các nút M ra khỏi N trong mỗi lần lặp cho đến khi mọi nút được "xử lý"], nhưng bây giờ tôi đã bỏ ý tưởng này) . Theo tôi, bản đồ đầu ra Job2 nên được giảm xuống, để tránh các quá trình sắp xếp/hợp nhất tốn kém, làm giảm hiệu suất.
Tôi cũng đã thực hiện cùng một thuật toán (3 công việc cũng như cùng một mẫu "giao tiếp", cũng là "Job2") cho nền tảng Giraph. Tuy nhiên Giraph là một nền tảng trong bộ nhớ và thuật toán cho cùng một bộ dữ liệu "có vấn đề" dẫn đến một OutOfMemoryException.
Đối với bất kỳ nhận xét, nhận xét, hướng dẫn nào tôi sẽ biết ơn.
CẬP NHẬT
tôi sẽ thay đổi thuật toán "quyết liệt". Tôi đã tìm thấy bài viết này Counting Triangles.
Khi mã được triển khai, tôi sẽ đăng ý kiến của mình ở đây và mã chi tiết hơn (nếu phương pháp này sẽ thành công).
UPDATE_2
Cuối cùng tôi đã kết thúc "sửa đổi" NodeIterator ++ thuật toán để nhu cầu của tôi (giấy Yahoo có sẵn thông qua một liên kết trong bài viết). Thật không may mặc dù tôi có thể thấy một sự cải thiện trong việc thực hiện kết quả cuối cùng là không tốt như tôi đã hy vọng. Kết luận tôi đã đạt được là cụm mà có sẵn cho tôi chỉ là quá nhỏ để làm cho các tính toán LCC khả thi cho các tập dữ liệu cụ thể này. Vì vậy, câu hỏi vẫn còn, hay đúng hơn là nó phát triển. Có ai biết một thuật toán phân phối/tuần tự hiệu quả để tính toán LCC hoặc hình tam giác với các nguồn lực hạn chế không? (Không có nghĩa là tôi nói rằng thuật toán NodeIterator ++ là xấu, tôi đơn giản nói rằng các tài nguyên có sẵn cho tôi là không đủ).
chỉ chụp trong bóng tối .. bạn đã thử [công việc phân cụm của mahout] (https://builds.apache.org/job/Mahout-Quality/javadoc/org/apache/mahout/graph/common/LocalClusteringCoefficientJob.html) –
Không, tôi sẽ xem xét điều đó. Thx cho một mẹo. – alien01
bạn có thể sửa nó không? Giảm() cho Job2 phát ra cái gì? –