Timeline for What is the computational complexity of the PageRank problem?
Current License: CC BY-SA 2.5
4 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Oct 6, 2010 at 3:15 | vote | accept | CommunityBot | ||
Oct 5, 2010 at 16:29 | comment | added | Joshua Grochow | @Kaveh: Well, I assume they update it on-the-fly, since I imagine computing it from scratch would be rather expensive. From that perspective this starts to get into streaming algorithms, distributed dynamic data structures, etc. I wonder what the best complexity of an update is? (But the OQ was simply about computing PageRank of a graph.) | |
Oct 5, 2010 at 14:51 | comment | added | Kaveh | Did Google compute the eigenvector directly each time or did they just update it each time the graph changed? | |
Oct 5, 2010 at 14:41 | history | answered | Joshua Grochow | CC BY-SA 2.5 |