Skip to main content

2018 | OriginalPaper | Buchkapitel

An Intra-algorithm Comparison Study of Complete Search FSM Implementations in Centralized Graph Transaction Databases

verfasst von : Rihab Ayed, Mohand-Saïd Hacid, Rafiqul Haque, Abderrazek Jemai

Erschienen in: Foundations of Intelligent Systems

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Frequent subgraph mining (FSM) algorithms are widely used in various areas of data analysis. Several experimental studies about FSM algorithms were reported in literature; however, these experiments lack some clarifications about the most efficient implementation of a specific algorithm for a context of use (e.g., medium size datasets). In this paper, we present an experimental study with available implementations of two well known complete search FSM algorithms namely gSpan and Gaston. Our main purpose of this experimental study is to find a suitable Frequent Subgraph Mining implementation for indexing centralized graphs databases for aggregated search(CAIR home page: www.​irit.​fr/​CAIR). In this paper, we provide details of the experimental results according to the input variation cases. We propose (for end users) a summary, about the most efficient FSM implementations for each algorithm (i.e., gSpan and Gaston), based on real datasets from the literature.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Contextual and Aggregated Information Retrieval: www.​irit.​fr/​CAIR.
 
2
Please refer to liris.​cnrs.​fr/​rihab.​ayed/​ESFSM.​pdf for references of algorithms and the list of all implementations.
 
4
For dataset links or MST strategies, see liris.​cnrs.​fr/​rihab.​ayed/​ESFSM.​pdf.
 
5
The lowest MST we tested in Table 5 is 1.5%.
 
6
We already contacted the authors about this issue.
 
7
Please refer to liris.​cnrs.​fr/​rihab.​ayed/​ESFSM.​pdf for more information.
 
Literatur
1.
Zurück zum Zitat Gago Alonso, A., Medina Pagola, J.E., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F.: Mining frequent connected subgraphs reducing the number of candidates. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008. LNCS (LNAI), vol. 5211, pp. 365–376. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87479-9_42CrossRef Gago Alonso, A., Medina Pagola, J.E., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F.: Mining frequent connected subgraphs reducing the number of candidates. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008. LNCS (LNAI), vol. 5211, pp. 365–376. Springer, Heidelberg (2008). https://​doi.​org/​10.​1007/​978-3-540-87479-9_​42CrossRef
2.
Zurück zum Zitat Inokuchi, A., Washio, T., Motoda, H.: An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data, pp. 13–23 (2000)CrossRef Inokuchi, A., Washio, T., Motoda, H.: An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data, pp. 13–23 (2000)CrossRef
3.
Zurück zum Zitat Kuramochi, M., Karypis, G.: Frequent subgraph discovery. In: Proceedings of the 2001 IEEE International Conference on Data Mining, ICDM 2001, pp. 313–320. IEEE Computer Society, Washington, DC (2001) Kuramochi, M., Karypis, G.: Frequent subgraph discovery. In: Proceedings of the 2001 IEEE International Conference on Data Mining, ICDM 2001, pp. 313–320. IEEE Computer Society, Washington, DC (2001)
6.
Zurück zum Zitat Nijssen, S., Kok, J.N.: A Quickstart in frequent structure mining can make a difference. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2004, pp. 647–652. ACM, New York (2004). https://doi.org/10.1145/1014052.1014134 Nijssen, S., Kok, J.N.: A Quickstart in frequent structure mining can make a difference. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2004, pp. 647–652. ACM, New York (2004). https://​doi.​org/​10.​1145/​1014052.​1014134
7.
Zurück zum Zitat Nijssen, S., Kok, J.N.: Frequent subgraph miners: Runtime dont say everything. In: Proceedings of the International Workshop on Mining and Learning with Graphs, MLG 2006, pp. 173–180 (2006) Nijssen, S., Kok, J.N.: Frequent subgraph miners: Runtime dont say everything. In: Proceedings of the International Workshop on Mining and Learning with Graphs, MLG 2006, pp. 173–180 (2006)
10.
Zurück zum Zitat Wörlein, M., Meinl, T., Fischer, I., Philippsen, M.: A Quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston. In: Jorge, A.M., Torgo, L., Brazdil, P., Camacho, R., Gama, J. (eds.) PKDD 2005. LNCS (LNAI), vol. 3721, pp. 392–403. Springer, Heidelberg (2005). https://doi.org/10.1007/11564126_39CrossRef Wörlein, M., Meinl, T., Fischer, I., Philippsen, M.: A Quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston. In: Jorge, A.M., Torgo, L., Brazdil, P., Camacho, R., Gama, J. (eds.) PKDD 2005. LNCS (LNAI), vol. 3721, pp. 392–403. Springer, Heidelberg (2005). https://​doi.​org/​10.​1007/​11564126_​39CrossRef
Metadaten
Titel
An Intra-algorithm Comparison Study of Complete Search FSM Implementations in Centralized Graph Transaction Databases
verfasst von
Rihab Ayed
Mohand-Saïd Hacid
Rafiqul Haque
Abderrazek Jemai
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-030-01851-1_8