Pagerank được tính toán theo cách phân phối như thế nào?

Question

Tôi hiểu ý tưởng đằng sau pagerank và đã thực hiện nó (khi đọc cuốn sách "lập trình trí thông minh tập thể").

Nhưng tôi đọc nó có thể được phân phối trên nhiều máy chủ (như tôi đoán là google đang làm). Tôi là một chút bối rối bởi vì theo sự hiểu biết của tôi, bạn cần toàn bộ đồ thị để làm xếp hạng trang trên nó vì mỗi thứ hạng liên quan đến xếp hạng của người khác.

Tôi đã tìm thấy wiki article nhưng không giải thích được nhiều.

Bất kỳ đề xuất nào về điều này có thể xảy ra? Ngoài ra, câu hỏi thưởng: là kỹ thuật để phân phối pagerank độc quyền cho pagerank hoặc phương pháp được sử dụng được áp dụng cho các thuật toán học máy khác được áp dụng cho đồ thị?

Answer 1

Cách tính toán nghệ thuật của PageRank hiện đại là với khung Google Pregel. Tôi khá chắc chắn rằng họ có một cái gì đó tinh vi hơn ngay bây giờ, nhưng đó là nỗ lực xuất bản mới nhất.

Bạn có thể đọc thêm chi tiết về nó trong research blog. Hoặc đọc bài báo đã xuất bản here.

Tôi đang làm việc trên phiên bản mã nguồn mở của mô hình Bulk Synchronous Parallel được gọi là Apache Hama. Ngoài ra còn có Apache Giraph mà chỉ tập trung vào các biểu đồ đồ thị và rất nhiều người khác.

Giống như mfrankli được đề cập, cũng có khung MapReduce (ví dụ Apache Hadoop) có thể được sử dụng để tính PageRank, nhưng nó không hiệu quả cho các thuật toán lặp lại.

Điều đáng lưu ý là cả hai giải pháp (MapReduce và BSP) là các giải pháp theo lô, vì vậy chúng có thể được sử dụng để tính toán lại PageRank cho đồ thị web hoàn chỉnh. Vì các cập nhật của Google nhanh hơn nhiều so với các thuật toán hàng loạt, bạn có thể mong đợi rằng chúng thường tính toán lại PageRank trên các biểu đồ con.

Answer 2

MapReduce cung cấp một số nền thú vị và có thể làm rõ cách bạn sẽ song song nhiệm vụ này.