As, I think, Page points out in the patent, PageRank's idea comes from Science Citation Index. That was an inverted list of scientific references, where you could look up an scientific paper in an expensive set of bound books and find all the papers in which it was later referenced. You can then use this to see who's getting referenced a lot, which is an ego trip in academia. Academic libraries had copies of that index. Now everybody has that kind of info, but when it had to be done by hand, it was hard.

Inverting the huge, sparse matrix of references for PageRank was expensive. Originally, Google did it about once a week. The big breakthrough was when someone (who?) figured out how to do it incrementally at scale.