Enhancing graph database indexing by suffix tree structure

Vincenzo Bonnici, Alfredo Ferro, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Biomedical and chemical databases are large and rapidly growing in size. Graphs naturally model such kinds of data. To fully exploit the wealth of information in these graph databases, scientists require systems that search for all occurrences of a query graph. To deal efficiently with graph searching, advanced methods for indexing, representation and matching of graphs have been proposed. This paper presents GraphGrepSX. The system implements efficient graph searching algorithms together with an advanced filtering technique. GraphGrepSX is compared with SING, GraphFind, CTree and GCoding. Experiments show that GraphGrepSX outperforms the compared systems on a very large collection of molecular data. In particular, it reduces the size and the time for the construction of large database index and outperforms the most popular systems.

Original languageEnglish (US)
Title of host publicationPattern Recognition in Bioinformatics - 5th IAPR International Conference, PRIB 2010, Proceedings
Pages195-203
Number of pages9
DOIs
StatePublished - 2010
Event5th IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2010 - Nijmegen, Netherlands
Duration: Sep 22 2010Sep 24 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6282 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2010
CountryNetherlands
CityNijmegen
Period9/22/109/24/10

Keywords

  • graph database search
  • indexing
  • molecular database
  • subgraph isomorphism
  • suffix tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Enhancing graph database indexing by suffix tree structure'. Together they form a unique fingerprint.

  • Cite this

    Bonnici, V., Ferro, A., Giugno, R., Pulvirenti, A., & Shasha, D. (2010). Enhancing graph database indexing by suffix tree structure. In Pattern Recognition in Bioinformatics - 5th IAPR International Conference, PRIB 2010, Proceedings (pp. 195-203). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6282 LNBI). https://doi.org/10.1007/978-3-642-16001-1_17