Có thể thực hiện pagerank mà không có toàn bộ tập dữ liệu không?

Question

Xin lỗi nếu điều này là ngu ngốc nhưng tôi đã chỉ nghĩ rằng tôi nên cung cấp cho một shot. Nói rằng tôi có một đồ thị thats rất lớn (ví dụ, 100 tỷ nút). Neo4J hỗ trợ 32 tỷ và những người khác hỗ trợ nhiều hơn hoặc ít hơn như nhau, vì vậy nói rằng tôi không thể có toàn bộ tập dữ liệu trong cơ sở dữ liệu cùng một lúc, tôi có thể chạy pagerank trên nó nếu đồ thị được chỉ dẫn (không có vòng lặp) và mỗi bộ kết nối đến tập hợp các nút tiếp theo (vì vậy sẽ không có liên kết mới nào được tạo ngược, chỉ các liên kết mới được tạo cho các tập hợp dữ liệu mới).

Có cách nào bằng cách nào đó tôi có thể lấy điểm số pagerank trước đó và áp dụng chúng cho bộ dữ liệu mới không? Tôi chỉ quan tâm đến pagerank cho tập dữ liệu gần đây nhất nhưng cần pagerank của tập trước để lấy dữ liệu bộ cuối cùng)?

Điều đó có hợp lý không? Nếu vậy, có thể làm được không?

Answer 1

Bạn cần tính toán nguyên tử riêng của một ma trận 100 tỷ 100 tỷ. Trừ khi nó cực kỳ thưa thớt, bạn không thể phù hợp với điều đó bên trong máy của bạn. Vì vậy, bạn cần một cách để tính toán các eigenvector hàng đầu của một ma trận khi bạn chỉ có thể nhìn vào một phần nhỏ của ma trận của bạn tại một thời điểm.

Phương pháp lặp để tính toán các biến riêng biệt chỉ yêu cầu bạn lưu một vài vectơ tại mỗi lần lặp (mỗi phần tử sẽ có 100 tỷ phần tử). Những người có thể phù hợp trên máy tính của bạn (với 4 byte nổi bạn sẽ cần khoảng 375GB cho mỗi vector). Một khi bạn có một vector ứng cử viên của bảng xếp hạng bạn có thể (rất chậm) áp dụng ma trận khổng lồ của bạn với nó bằng cách đọc ma trận trong khối (vì bạn có thể xem 32 tỷ hàng tại một thời điểm bạn sẽ cần chỉ hơn 3 khối). Lặp lại quá trình này và bạn sẽ có các khái niệm cơ bản về phương thức nguồn được sử dụng trong pagerank. cf http://www.ams.org/samplings/feature-column/fcarc-pagerank và http://en.wikipedia.org/wiki/Power_iteration

Tất nhiên yếu tố giới hạn ở đây là số lần bạn cần kiểm tra ma trận. Nó chỉ ra rằng bằng cách lưu trữ nhiều hơn một vector ứng cử viên và sử dụng một số thuật toán ngẫu nhiên bạn có thể có được độ chính xác tốt với ít lần đọc dữ liệu của bạn. Đây là một chủ đề nghiên cứu hiện tại trong thế giới toán học được áp dụng. Bạn có thể tìm thêm thông tin tại đây http://arxiv.org/abs/0909.4061, tại đây http://arxiv.org/abs/0909.4061 và tại đây http://arxiv.org/abs/0809.2274. Có mã sẵn có tại đây: http://code.google.com/p/redsvd/ nhưng bạn không thể chỉ sử dụng mã đó cho các kích thước dữ liệu mà bạn đang nói đến.

Một cách khác mà bạn có thể thực hiện là xem xét "svd gia tăng" có thể phù hợp với vấn đề của bạn tốt hơn nhưng phức tạp hơn một chút. Hãy xem xét lưu ý này: http://www.cs.usask.ca/~spiteri/CSDA-06T0909e.pdf và diễn đàn này: https://mathoverflow.net/questions/32158/distributed-incremental-svd