Download SPAWC: A Scalable Parallel Web Crawler

Transcript
Computer Science 9868
SPAWC: A Scalable Parallel Web Crawler
Jeffrey Shantz <jshantz(5-1)@csd.uwo.ca>
June 02, 2010
Let i, j ∈ V be any pair of vertices such that T [i, j] ∧ T [j, i] = 0 before the insertion of edge (u, v).
As such, i and j reside in separate strongly-connected components SCCi and SCCj before the
insertion of (u, v). Now, suppose that after inserting (u, v) and executing the Transitive-Closure
algorithm, T [i, j] = T [j, i] = 1. Then, the insertion of (u, v) has created a path i
j
i in G.
Let k be an arbitrary vertex in SCCi , and ` be an arbitrary vertex in SCCj . By definition of SCCi ,
there exists a path k
i
k. Similarly, by definition of SCCj , there exists a path `
Finally, since there exists a path i
i
j
i, then there also exists a path k
i
j
j
`
`.
j
k. As such, there is a path between every vertex pair k, ` ∈ SCCi ∪ SCCj , and so SCCi and
SCCj must be merged when T [i, j] = T [j, i] = 1. This situation is depicted in Figure 11.
i
SCC i
j
SCC j
Figure 11: Merging strongly-connected components
SCC-Naı̈ve-Add-Edge iterates through every node pair (i, j) ∈ V , checking if T [i, j] = T [j, i] = 1.
If this is the case, then the components SCCi and SCCj are merged, and therefore the dynamic
SCC problem is solved by the SCC-Naı̈ve-Add-Edge algorithm.
6.2
Algorithm 1
Traditionally, a transitive closure matrix T for a graph G = (V, E) having n vertices is represented
as a sequence of n × n values – perhaps integers or bytes. Each cell T [i, j] for some i, j ∈ V is a
binary value, and thus one can compactly represent T as a matrix of bits.
Let b be the number of bits in an integral data type to be used to store transitive closure values in
T . Then, to represent an n × n transitive closure matrix, one need store n rows, each consisting of
B = d nb e blocks. For instance, if one wishes to store a transitive closure matrix for a graph having
2000 vertices, and 64 bit integers are used in the matrix, then each row of the matrix can be stored
in d 2000
64 e = 32 64-bit integer blocks. Since the matrix will contain 2000 rows, a total of 2000 rows
× 32 blocks/row × 64 bits/block = 4, 096, 000 bits or 500 KB will be used.
This is in contrast to a traditional transitive closure matrix defined, for instance, using n × n
bytes. In the same graph of 2000 vertices, such a matrix will consume (2000 × 2000) bytes × 8
bits/byte = 32, 000, 000 bits or nearly 4 MB. Figure 12 compares the byte matrix with the bit
matrix approach, showing the total space consumption of each approach for increasing graph sizes.
Since each of the n × n cells in the bit matrix is represented in a single bit, the space complexity
27