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