{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T15:12:41Z","timestamp":1723907561600},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2010,12]]},"abstract":"Abstract<\/jats:title>\n \n Background<\/jats:title>\n Finding the subgraphs of a graph database that are isomorphic to a given query graph has practical applications in several fields, from cheminformatics to image understanding. Since subgraph isomorphism is a computationally hard problem, indexing techniques have been intensively exploited to speed up the process. Such systems filter out those graphs which cannot contain the query, and apply a subgraph isomorphism algorithm to each residual candidate graph. The applicability of such systems is limited to databases of small graphs, because their filtering power degrades on large graphs.<\/jats:p>\n <\/jats:sec>\n \n Results<\/jats:title>\n In this paper, SING (Subgraph search In Non-homogeneous Graphs), a novel indexing system able to cope with large graphs, is presented. The method uses the notion of feature<\/jats:italic>, which can be a small subgraph, subtree or path. Each graph in the database is annotated with the set of all its features. The key point is to make use of feature locality information. This idea is used to both improve the filtering performance and speed up the subgraph isomorphism task.<\/jats:p>\n <\/jats:sec>\n \n Conclusions<\/jats:title>\n Extensive tests on chemical compounds, biological networks and synthetic graphs show that the proposed system outperforms the most popular systems in query time over databases of medium and large graphs. Other specific tests show that the proposed system is effective for single large graphs.<\/jats:p>\n <\/jats:sec>","DOI":"10.1186\/1471-2105-11-96","type":"journal-article","created":{"date-parts":[[2010,2,19]],"date-time":"2010-02-19T18:58:33Z","timestamp":1266605913000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":46,"title":["SING: Subgraph search In Non-homogeneous Graphs"],"prefix":"10.1186","volume":"11","author":[{"given":"Raffaele","family":"Di Natale","sequence":"first","affiliation":[]},{"given":"Alfredo","family":"Ferro","sequence":"additional","affiliation":[]},{"given":"Rosalba","family":"Giugno","sequence":"additional","affiliation":[]},{"given":"Misael","family":"Mongiov\u00ec","sequence":"additional","affiliation":[]},{"given":"Alfredo","family":"Pulvirenti","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Shasha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,2,19]]},"reference":[{"issue":"4","key":"3553_CR1","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/1114244.1114248","volume":"30","author":"X Yan","year":"2005","unstructured":"Yan X, Yu PS, Han J: Graph Indexing Based on Discriminative Frequent Structure Analysis. ACM Transactions on Database Systems 2005, 30(4):960\u2013993. 10.1145\/1114244.1114248","journal-title":"ACM Transactions on Database Systems"},{"key":"3553_CR2","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1145\/1247480.1247574","volume-title":"Proceedings of ACM SIGMOD international conference on Management of data","author":"J Cheng","year":"2007","unstructured":"Cheng J, Ke Y, Ng W, Lu A: Fg-index: towards verification-free query processing on graph databases. Proceedings of ACM SIGMOD international conference on Management of data 2007, 857\u2013872."},{"key":"3553_CR3","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1109\/ICDE.2007.368956","volume-title":"Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on","author":"DW Williams","year":"2007","unstructured":"Williams DW, Huan J, Wang W: Graph Database Indexing Using Structured Graph Decomposition. Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on 2007, 976\u2013985. full_text"},{"key":"3553_CR4","first-page":"38","volume-title":"ICDE '06: Proceedings of the 22nd International Conference on Data Engineering","author":"H He","year":"2006","unstructured":"He H, Singh AK: Closure-Tree: An Index Structure for Graph Queries. In ICDE '06: Proceedings of the 22nd International Conference on Data Engineering. Washington, DC, USA: IEEE Computer Society; 2006:38."},{"key":"3553_CR5","first-page":"112","volume":"2","author":"R Giugno","year":"2002","unstructured":"Giugno R, Shasha D: Graphgrep: A fast and universal method for querying graphs. Pattern Recognition, 2002. Proceedings. 16th International Conference on 2002, 2: 112\u2013115.","journal-title":"Pattern Recognition, 2002. Proceedings. 16th International Conference on"},{"key":"3553_CR6","doi-asserted-by":"crossref","unstructured":"Ferro A, Giugno R, Mongiovi M, Pulvirenti A, Skripin D, Shasha D: GraphFind: enhancing graph searching by low support data mining techniques. BMC Bioinformatics 2008., (9):","DOI":"10.1186\/1471-2105-9-S4-S10"},{"key":"3553_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1145\/1353343.1353369","volume-title":"EDBT '08: Proceedings of the 11th international conference on Extending database technology","author":"L Zou","year":"2008","unstructured":"Zou L, Chen L, Yu JX, Lu Y: A novel spectral coding in a large graph database. In EDBT '08: Proceedings of the 11th international conference on Extending database technology. New York, NY, USA: ACM; 2008:181\u2013192. full_text"},{"key":"3553_CR8","first-page":"181","volume-title":"Proceedings of IEEE 23rd International Conference on Data Engineering","author":"S Zhang","year":"2007","unstructured":"Zhang S, Hu M, Yang J: TreePi: A Novel Graph Indexing Method. Proceedings of IEEE 23rd International Conference on Data Engineering 2007, 181\u2013192."},{"key":"3553_CR9","first-page":"938","volume-title":"VLDB '07: Proceedings of the 33rd international conference on Very large data bases","author":"P Zhao","year":"2007","unstructured":"Zhao P, Yu JX, Yu PS: Graph indexing: tree + delta \u2264 graph. In VLDB '07: Proceedings of the 33rd international conference on Very large data bases. VLDB Endowment; 2007:938\u2013949."},{"key":"3553_CR10","unstructured":"NCI DTP Antiviral Screen data[http:\/\/dtp.nci.nih.gov\/docs\/aids\/aids_data.html]"},{"key":"3553_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"J Ullmann","year":"1976","unstructured":"Ullmann J: An algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery 1976, 23: 31\u201342.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"10","key":"3553_CR12","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"L Cordella","year":"2004","unstructured":"Cordella L, Foggia P, Sansone C, Vento M: A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 2004, 26(10):1367\u20131372. 10.1109\/TPAMI.2004.75","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"11","key":"3553_CR13","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","volume":"20","author":"N Kashtan","year":"2004","unstructured":"Kashtan N, Itzkovitz S, Milo R, Alon U: Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 2004, 20(11):1746\u20131758. 10.1093\/bioinformatics\/bth163","journal-title":"Bioinformatics"},{"key":"3553_CR14","unstructured":"National Center for Biotechnology Information[http:\/\/www.ncbi.nlm.nih.gov\/]"},{"key":"3553_CR15","first-page":"D535","volume-title":"Nucleic Acids Res","author":"C Stark","year":"2006","unstructured":"Stark C, Breitkreutz BJ, Reguly T, Boucher L, Breitkreutz A, Tyers M: BioGRID: a general repository for interaction datasets. Nucleic Acids Res 2006, (34 Database):D535\u20139. 10.1093\/nar\/gkj109"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-96.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T05:23:21Z","timestamp":1630473801000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-11-96"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2,19]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["3553"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-11-96","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2,19]]},"assertion":[{"value":"29 July 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"96"}}