Managing and Mining Graph Data part 22 is a comprehensive survey book in graph data analytics. It contains extensive surveys on important graph topics such as graph languages, indexing, clustering, data generation, pattern mining, classification, keyword search, pattern matching, and privacy. It also studies a number of domain-specific scenarios such as stream mining, web graphs, social networks, chemical and biological data. The chapters are written by leading researchers, and provide a broad perspective of the area. This is the first comprehensive survey book in the emerging topic of graph data processing. . | 1992 MANAGING AND MINING GRAPH DATA Algorithm 2 Compute-Chain-Cover G C1 C2 C Input The DAG G and hi chain cover C1 C Output The chain cover code for every node in G 1 sort at- nodes in G in topological order 2 let every node vi in G unmarked 3 whil e there are unmarked no de vi in G that do not have unmarked immediate ruccessors do 4 chaincode vi 1 to 2 to fc to 5 let Li x denote the x-th pair in chaincode 6 let suc vi denote the immediate successors of vi in G 7 for every Vj G suc vi do 8 for I 1 to fc do 9 Jlpjj Lj l 10 l pi i Li i in if pj i pi l then 12 Li i l pj i 13 end if 14 end for 15 end for 16 mark vi 17 end while 18 return the tef of chaincode vi for every vi G G all cheins is the entire set of nodes in G and the intersection of nodes in any two chains is empty. The optimal chain cover of G is a cham cover of G that contains the least number of chaim among all possible chain covers of G. Suppose the chain cover contains fc chrins to answer the reachability queries eaeh node vi G G is assiened a code denote chaincode vi which is a lis- of pairs 1 pii 2 pi 2 fc pi k . Each pair j pij means that tire node vi crn reach any nodes from the position pi j in the j-th chaie. If vi cannot reech any node in the j-th chain then pi j to. The chain cover index contains chaincode vi for every node vi in G. AV aeachebility query va vd cm be answered uaing a predicate Pc such that va vd is true if and only if va appears al the pa j position ltd a chain Cj and pd j pa j. In other words va crn reach vd in a chain Cj. All pairs m the chrin eoeeoi index for G crn be indexed and itored using a B -tree. Answering a riitic itii bir t j query nee ds O log n time with O n fc space. Gitin at chain cover C1 C2 . ef a DAG G A-gorithm 29 shows how to compute chaincode vi for evoy vi G G. It visite every node in G in the rcvcrec of topological order Ime 3i. Foe each node visited its chaincode vi is updated using ite irn mediate successors if the eorcesponding position in the l-th .
