|
Title:
|
ANALYZING EFFICIENT EMBEDDING LIST STRUCTURES IN SUBGRAPH MINING |
|
Author(s):
|
Nivin A. Helal , Taysir H. A. Soliman , Omar H. Karam |
|
ISBN:
|
978-972-8924-40-9 |
|
Editors:
|
Jörg Roth, Jairo Gutiérrez and Ajith P. Abraham (series editors: Piet Kommers, Pedro Isaías and Nian-Shing Chen) |
|
Year:
|
2007 |
|
Edition:
|
Single |
|
Keywords:
|
Graph Mining, Subgraph Isomorphism, Embedding Lists. |
|
Type:
|
Short Paper |
|
First Page:
|
129 |
|
Last Page:
|
134 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Frequent Subgraph Mining has been an active research topic in data mining because of its wide-range application areas,
such as video indexing, XML document clustering, and Bioinformatics. The problem of subgraph mining is to find
frequent subgraphs over a set of graphs, which requires efficient enumeration of all frequent subgraphs and subgraph
isomorphism. As the problem of subgraph isomorphism is NP-complete, known approaches either trade time to perform
subgraph isomorphism testing versus storage and keep embeddings to map the nodes and edges of a subgraph to their
corresponding nodes and edges in the graph it occurs in. In this paper, we are analyzing the effect of different Embedding
List (EL) structures on both runtime and memory usage. We re-implemented the Fast Frequent Subgraph Mining (FFSM)
algorithm using its normal structure of EL, and also applied to it another EL structure (ELE). We applied both algorithms
on a synthetic dataset, a chemical compound dataset, and a 3D structure protein dataset. Results show that our EL
structure FFSM (ELE) is faster than FFSM by an average of 2.4 seconds. |
|
|
|
|
|
|
