{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:18:52Z","timestamp":1775837932357,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            Graphs are of growing importance in modeling complex structures such as chemical compounds, proteins, images, and program dependence. Given a query graph\n            <jats:italic>Q<\/jats:italic>\n            , the\n            <jats:italic>subgraph isomorphism<\/jats:italic>\n            problem is to find a set of graphs containing\n            <jats:italic>Q<\/jats:italic>\n            from a graph database, which is NP-complete. Recently, there have been a lot of research efforts to solve the subgraph isomorphism problem for a large graph database by utilizing graph indexes. By using a graph index as a filter, we prune graphs that are not real answers at an inexpensive cost. Then, we need to use expensive subgraph isomorphism tests to verify filtered candidates only. This way, the number of disk I\/Os and subgraph isomorphism tests can be significantly minimized. The current practice for experiments in graph indexing techniques is that the author of a newly proposed technique does not implement existing indexes on his own code base, but instead uses the original authors' binary executables and reports only the wall clock time. However, we observe this practice may result in several problems. In order to address these problems, we have made significant efforts in implementing all representative indexing methods on a common framework called iGraph. Unlike existing implementations which either use (full or partial) in-memory representations or rely on OS file system cache without guaranteeing real disk I\/Os, we have implemented these indexes on top of a storage engine that guarantees real disk I\/Os. Through extensive experiments using many synthetic and real datasets, we also provide new empirical findings in the performance of the full disk-based implementations of these methods.\n          <\/jats:p>","DOI":"10.14778\/1920841.1920901","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"449-459","source":"Crossref","is-referenced-by-count":83,"title":["iGraph"],"prefix":"10.14778","volume":"3","author":[{"given":"Wook-Shin","family":"Han","sequence":"first","affiliation":[{"name":"Kyungpook National University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinsoo","family":"Lee","sequence":"additional","affiliation":[{"name":"Kyungpook National University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minh-Duc","family":"Pham","sequence":"additional","affiliation":[{"name":"Kyungpook National University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/www.seagate.com.  http:\/\/www.seagate.com."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/msdn.microsoft.com\/en-us\/library\/cc644950(VS.85).aspx.  http:\/\/msdn.microsoft.com\/en-us\/library\/cc644950(VS.85).aspx."},{"key":"e_1_2_1_3_1","unstructured":"Aids antiviral dataset used for gindex. http:\/\/www.xifengyan.net\/software.htm.  Aids antiviral dataset used for gindex. http:\/\/www.xifengyan.net\/software.htm."},{"key":"e_1_2_1_4_1","unstructured":"Gaston. http:\/\/www.liacs.nl\/snijssen\/gaston\/iccs.html.  Gaston. http:\/\/www.liacs.nl\/snijssen\/gaston\/iccs.html."},{"key":"e_1_2_1_5_1","unstructured":"gboost. http:\/\/www.kyb.mpg.de\/bs\/people\/nowozin\/gboost\/.  gboost. http:\/\/www.kyb.mpg.de\/bs\/people\/nowozin\/gboost\/."},{"key":"e_1_2_1_6_1","unstructured":"Graphgen --- a synthetic graph data generator. http:\/\/www.cse.ust.hk\/graphgen\/.  Graphgen --- a synthetic graph data generator. http:\/\/www.cse.ust.hk\/graphgen\/."},{"key":"e_1_2_1_7_1","unstructured":"National cancer institute. http:\/\/dtp.nci.nih.gov\/.  National cancer institute. http:\/\/dtp.nci.nih.gov\/."},{"key":"e_1_2_1_8_1","unstructured":"The pubchem project. pubchem.ncbi.nlm.nih.gov.  The pubchem project. pubchem.ncbi.nlm.nih.gov."},{"key":"e_1_2_1_9_1","unstructured":"Vf2 library. http:\/\/amalfi.dis.unina.it\/graph\/db\/vflib-2.0\/.  Vf2 library. http:\/\/amalfi.dis.unina.it\/graph\/db\/vflib-2.0\/."},{"key":"e_1_2_1_10_1","first-page":"169","volume-title":"The VLDB Journal","author":"Ailamaki A.","year":"2001","unstructured":"A. Ailamaki , D. DeWitt , M. Hill , and M. Skounakis . Weaving relations for cache performance . The VLDB Journal , pages 169 -- 180 , 2001 . A. Ailamaki, D. DeWitt, M. Hill, and M. Skounakis. Weaving relations for cache performance. The VLDB Journal, pages 169--180, 2001."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.1.235"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.37"},{"key":"e_1_2_1_15_1","volume-title":"ICDM, page 549","author":"Huan J.","year":"2003","unstructured":"J. Huan , W. Wang , and J. Prins . Efficient mining of frequent subgraphs in the presence of isomorphism . In ICDM, page 549 , 2003 . J. Huan, W. Wang, and J. Prins. Efficient mining of frequent subgraphs in the presence of isomorphism. In ICDM, page 549, 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081706.1081753"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.599932"},{"key":"e_1_2_1_18_1","volume-title":"Database Management Systems","author":"Ramakrishnan R.","year":"2003","unstructured":"R. Ramakrishnan and J. Gehrke . Database Management Systems . McGraw-Hill, Inc. , New York, NY, USA , 2003 . R. Ramakrishnan and J. Gehrke. Database Management Systems. McGraw-Hill, Inc., New York, NY, USA, 2003."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.diin.2007.06.011"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564126_39"},{"key":"e_1_2_1_25_1","first-page":"721","volume-title":"ICDM","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gspan: Graph-based substructure pattern mining . In ICDM , pages 721 -- 724 , 2002 . X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In ICDM, pages 721--724, 2002."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114248"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368955"},{"key":"e_1_2_1_30_1","first-page":"938","volume-title":"VLDB","author":"Zhao P.","year":"2007","unstructured":"P. Zhao , J. X. Yu , and P. S. Yu . Graph indexing: Tree + delta &gt;= graph . In VLDB , pages 938 -- 949 , 2007 . P. Zhao, J. X. Yu, and P. S. Yu. Graph indexing: Tree + delta &gt;= graph. In VLDB, pages 938--949, 2007."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353369"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:46:27Z","timestamp":1672227987000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920901"}},"subtitle":["a framework for comparisons of disk-based graph indexing techniques"],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920901"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920901","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}