TALE: A Tool forApproximate Large Graph Matchin
Largegraphdatasets arecommoninmanyemerg ingdatabase applications, andmostnotably inlarge scale sci entific applications. Tofully exploit thewealthofinformation encoded ingraphs, effective andefficient graphmatching tools arecritical. Duetothenoisyaiid incomplete iiature ofreal graphdatasets, approximate, rather thanexact, graphmatching is required. Furthermore, manymodernapplications needtoquery large graphs, eachofwhichhashundreds tothousands ofnodes andedges. Thispaperpresents anovel technique forapproximate match ingoflarge graphqueries. We propose anovel indexing method thatincorporates graphstructural information ina hybrid indexstructure. Thisindexing technique achieves highprining powerandtheindexsize scales linearly withthedatabase size. Inaddition, we propose aninnovative matching paradigm to querylarge graphs. Thistechnique distinguishes nodesbytheir importance inthegraphstructure. Thematching algorithm first matches theimportant nodesofaqueryandthenprogressively extends thesematches. Throughexperiments on several real datasets, this paperdemonstrates theeffectiveness andefficiency oftheproposed method.