TY - GEN
T1 - gSpan
T2 - 2nd IEEE International Conference on Data Mining, ICDM '02
AU - Yan, Xifeng
AU - Han, Jiawei
PY - 2002
Y1 - 2002
N2 - We investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called gSpan (graph-based Substructure pattern mining), which discovers frequent substructures without candidate generation. gSpan builds a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order, gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Our performance study shows thai gSpan substantially outperforms previous algorithms, sometimes by an order of magnitude.
AB - We investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called gSpan (graph-based Substructure pattern mining), which discovers frequent substructures without candidate generation. gSpan builds a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order, gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Our performance study shows thai gSpan substantially outperforms previous algorithms, sometimes by an order of magnitude.
UR - http://www.scopus.com/inward/record.url?scp=78149333073&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78149333073&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:78149333073
SN - 0769517544
SN - 9780769517544
T3 - Proceedings - IEEE International Conference on Data Mining, ICDM
SP - 721
EP - 724
BT - Proceedings - 2002 IEEE International Conference on Data Mining, ICDM 2002
Y2 - 9 December 2002 through 12 December 2002
ER -