PageRank (cont)
Costs for computing PageRank for each representation:
| Representation | |
linkExists(v,w) | |
Cost |
| Adj. matrix | |
edge[v][w] | |
V.1 |
| Adj. lists | |
search(w,list[v]) | |
V.(E/V) = E |
| Adj. sets | |
isElem(w,set[v]) | |
V.log(E/V) |
Not feasible ... V ≅ 4×1010 ⇒ matrix has 1021 cells
I.e. we can't store the entire web as a Graph structure
So how to really do it?
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}