{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:34:08Z","timestamp":1760708048189,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["617808"],"award-info":[{"award-number":["617808"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>\n            We study the problem of processing\n            <jats:italic>subgraph queries<\/jats:italic>\n            on a database that consists of a set of graphs. The answer to a subgraph query is the set of graphs in the database that are supergraphs of the query. In this article, we propose an efficient index,\n            <jats:italic>FG*-index<\/jats:italic>\n            , to solve this problem.\n          <\/jats:p>\n          <jats:p>\n            The cost of processing a subgraph query using most existing indexes mainly consists of two parts: the\n            <jats:italic>index probing<\/jats:italic>\n            cost and the\n            <jats:italic>candidate verification<\/jats:italic>\n            cost. Index probing is to find the query in the index, or to find the graphs from which we can generate a candidate answer set for the query. Candidate verification is to test whether each graph in the candidate set is indeed a supergraph of the query. We design FG*-index to minimize these two costs as follows.\n          <\/jats:p>\n          <jats:p>\n            FG*-index consists of three components: the\n            <jats:italic>FG-index<\/jats:italic>\n            , the\n            <jats:italic>feature-index<\/jats:italic>\n            , and the\n            <jats:italic>FAQ-index<\/jats:italic>\n            . First, the FG-index employs the concept of\n            <jats:italic>Frequent subGraph<\/jats:italic>\n            (\n            <jats:italic>FG<\/jats:italic>\n            ) to allow the set of queries that are FGs to be answered without candidate verification. We call this set of queries\n            <jats:italic>FG-queries<\/jats:italic>\n            . We can enlarge the set of FG-queries so that more queries can be answered without candidate verification; however, a larger set of FG-queries implies a larger FG-index and hence the index probing cost also increases. We propose the feature-index to reduce the index probing cost. The feature-index uses features to filter false results that are matched in the FG-index, so that we can quickly find the truly matching graphs for a query. For processing non-FG-queries, we propose the FAQ-index, which is dynamically constructed from the set of\n            <jats:italic>Frequently Asked non-FG-Queries<\/jats:italic>\n            (\n            <jats:italic>FAQs<\/jats:italic>\n            ). Using the FAQ-index, verification is not required for processing FAQs and only a small number of candidates need to be verified for processing non-FG-queries that are\n            <jats:italic>not frequently asked<\/jats:italic>\n            . Finally, a comprehensive set of experiments verifies that query processing using FG*-index is up to orders of magnitude more efficient than state-of-the-art indexes and it is also more scalable.\n          <\/jats:p>","DOI":"10.1145\/1508857.1508859","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:14:44Z","timestamp":1240323284000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Efficient query processing on graph databases"],"prefix":"10.1145","volume":"34","author":[{"given":"James","family":"Cheng","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Yiping","family":"Ke","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, New Territories, Hong Kong"}]},{"given":"Wilfred","family":"Ng","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2009,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872776"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-007-0084-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-007-0042-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3227207.3227306"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT'04)","author":"Cheng J.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014068"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'97)","author":"Goldman R.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'94)","year":"1994","author":"Guting R. H.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.37"},{"volume-title":"Proceedings of the Workshop at the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'94)","author":"Holder L. B.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/974614.974655"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014123"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645804.669817"},{"key":"e_1_2_1_18_1","unstructured":"James C. A. Weininger D. and Delany J. 2003. Daylight theory manual daylight version 4.82. Daylight Chemical Information Systems Inc.  James C. A. Weininger D. and Delany J. 2003. Daylight theory manual daylight version 4.82. Daylight Chemical Information Systems Inc."},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'07)","author":"Jiang H.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564707"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281236"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.86"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150432"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'02)","author":"Manku G. S.","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT'99)","author":"Milo T.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA'07)","author":"Ng W.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'03)","author":"Srinivasa S.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'07)","author":"Williams D. W.","key":"e_1_2_1_31_1"},{"volume-title":"Proceedings of the IEEE International Conference on Data Mining (ICDM'02)","author":"Yan X.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114248"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'04)","author":"Yu J. X.","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'06)","author":"Zhang N.","key":"e_1_2_1_37_1"},{"volume-title":"Proceedings of the International Conference on Data Mining (ICDE'07)","author":"Zhang S.","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'07)","author":"Zhao P.","key":"e_1_2_1_39_1"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508859","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1508857.1508859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:42Z","timestamp":1750253382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1508857.1508859"],"URL":"https:\/\/doi.org\/10.1145\/1508857.1508859","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2007-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}