I’m curious to know how Google stores the matrix that’s used in the PageRank algorithm; and am looking for a data-structure for storing a very-large (not fitting in memory of any one computer) sparse matrix, and efficiently (not sure what that means yet) performing operations on it.
If there’s a white-paper available please post a link or a title (I’ve done some research, and couldn’t find one), and if not, it would be great if you could post links or just names of papers or books that would help get me started.
In my initial research I found the sparse row-wise format [1], and I started reading Sparse Matrix Technology [2]; so please let me if I’m on the right track here.
- [1] Chang, 1969 Curtis and Reid, 1971 Gustavson, 1972
- [2] Pissanetzky, 1984
2
It really depends on the scale you have in mind. Sparse matrices will only take you that far… For Google and similar very large scale applications, think more along the line of distributed databases.
Just to mention, there are indeed several papers available (via Google Scholar, say) that discuss Google’s approach to distributed storage (BigTable), or Amazon’s (SimpleDB), etc. There is also an open source system called Hypertable, which can run on top of Apache Hadoop for instance.
If you’re really interested in sparse matrices, I think Davis (2006) is a very decent text, and very up-to-date. The book also includes the CSparse package, ready to use. (I don’t have direct experience with it so I cannot comment on scalability…) Note that the author’s personal web site lists other packages and resources, as well, such as SuiteSparse.
1