Bộ phân chia trên tia lửa apache

Question

Tôi đang cố gắng tìm thuật toán tìm kiếm các bộ phân tách (các thành phần được kết nối/liên kết tìm) trên lượng lớn dữ liệu với tia lửa apache. Vấn đề là lượng dữ liệu. Ngay cả biểu diễn thô của đỉnh biểu đồ không phù hợp với ram trên một máy đơn lẻ. Cạnh cũng không phù hợp với ram.

Dữ liệu nguồn là tệp văn bản của các cạnh đồ thị trên hdfs: "id1 \ t id2".

id hiện tại dưới dạng giá trị chuỗi, không phải int.

giải pháp Naive mà tôi tìm thấy là:

1. mất RDD cạnh ->[id1:id2] [id3:id4] [id1:id3]
2. nhóm cạnh bằng chìa khóa. ->[id1:[id2;id3]][id3:[id4]]
3. cho mỗi bản ghi thiết lập id tối thiểu cho từng nhóm ->(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. ngược RDD từ giai đoạn 3 [id2:id1] -> [id1:id2]
5. leftOuterJoin của rdds từ giai đoạn 3 và 4
6. lặp lại từ giai đoạn 2 trong khi kích thước của RDD trên bước 3 sẽ không thay đổi

Nhưng kết quả này trong việc chuyển một lượng lớn dữ liệu giữa các nút (xáo trộn)

Bất kỳ lời khuyên nào?

Answer 1

Nếu bạn đang làm việc với đồ thị tôi sẽ đề nghị rằng bạn hãy nhìn vào hoặc là một trong những thư viện

• GraphX
• GraphFrames

Cả hai đều cung cấp các thuật toán thành phần kết nối ra khỏi cái hộp.

GraphX ​​:

val graph: Graph = ... 
val cc = graph.connectedComponents().vertices 

GraphFrames:

val graph: GraphFrame = ... 
val cc = graph.connectedComponents.run() 
cc.select("id", "component").orderBy("component").show()