{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:32:37Z","timestamp":1791916357597,"version":"4.3.4"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319181196","type":"print"},{"value":"9783319181202","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18120-2_18","type":"book-chapter","created":{"date-parts":[[2015,4,8]],"date-time":"2015-04-08T04:08:06Z","timestamp":1428466086000},"page":"299-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Fast Subgraph Matching on Large Graphs using Graphics Processors"],"prefix":"10.1007","author":[{"given":"Ha-Nguyen","family":"Tran","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jung-jae","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,4,9]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"He, H., Singh, A.K.: Graphs-at-a-time: query language and access methods for graph databases. In: SIGMOD, pp. 405\u2013418 (2008)","DOI":"10.1145\/1376616.1376660"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Kasneci, G., Suchanek, F.M., Ifrim, G., Ramanath, M., Weikum, G.: Naga: Searching and ranking knowledge. In: ICDE, pp. 953\u2013962 (2008)","DOI":"10.1109\/ICDE.2008.4497504"},{"issue":"1\u20132","key":"18_CR3","first-page":"340","volume":"3","author":"P Zhao","year":"2010","unstructured":"Zhao, P., Han, J.: On graph query optimization in large networks. PVLDB 3(1\u20132), 340\u2013351 (2010)","journal-title":"PVLDB"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structure-based approach. In: SIGMOD, pp. 335\u2013346 (2004)","DOI":"10.1145\/1007568.1007607"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: STOC, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"18_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann, J.R.: An algorithm for subgraph isomorphism. JACM 23(1), 31\u201342 (1976)","journal-title":"JACM"},{"issue":"10","key":"18_CR7","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub) graph isomorphism algorithm for matching large graphs. PAMI 26(10), 1367\u20131372 (2004)","journal-title":"PAMI"},{"issue":"1","key":"18_CR8","first-page":"364","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. PVLDB 1(1), 364\u2013375 (2008)","journal-title":"PVLDB"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Zhang, S., Li, S., Yang, J.: GADDI: distance index based subgraph matching in biological networks. In: EDBT, pp. 192\u2013203 (2009)","DOI":"10.1145\/1516360.1516384"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1671970.1921702","volume":"15","author":"JR Ullmann","year":"2010","unstructured":"Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. JEA 15, 1\u20136 (2010)","journal-title":"JEA"},{"key":"18_CR11","unstructured":"Han, W.S., Lee, J., Lee, J.H.: Turbo iso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD, pp. 337\u2013348 (2013)"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/978-3-642-20149-3_30","volume-title":"Database Systems for Advanced Applications","author":"S Kim","year":"2011","unstructured":"Kim, S., Song, I., Lee, Y.J.: An edge-based framework for fast subgraph matching in a large graph. In: Yu, J.X., Kim, M.H., Unland, R. (eds.) DASFAA 2011, Part I. LNCS, vol. 6587, pp. 404\u2013417. Springer, Heidelberg (2011)"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Brocheler, M., Pugliese, A., Subrahmanian, V.S.: COSI: Cloud oriented subgraph identification in massive social networks. In: ASONAM, pp. 248\u2013255 (2010)","DOI":"10.1109\/ASONAM.2010.80"},{"issue":"9","key":"18_CR14","first-page":"788","volume":"5","author":"Z Sun","year":"2012","unstructured":"Sun, Z., Wang, H., Wang, H., Shao, B., Li, J.: Efficient subgraph matching on billion node graphs. PVLDB 5(9), 788\u2013799 (2012)","journal-title":"PVLDB"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-540-77220-0_21","volume-title":"High Performance Computing \u2013 HiPC 2007","author":"P Harish","year":"2007","unstructured":"Harish, P., Narayanan, P.J.: Accelerating large graph algorithms on the GPU using CUDA. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) HiPC 2007. LNCS, vol. 4873, pp. 197\u2013208. Springer, Heidelberg (2007)"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Merrill, D., Garland, M., Grimshaw, A.: Scalable GPU graph traversal. In: PPoPP, pp. 117\u2013128 (2012)","DOI":"10.1145\/2370036.2145832"},{"key":"18_CR17","unstructured":"Katz, G.J., Kider Jr., J.T.: All-pairs shortest-paths for large graphs on the GPU. In: GH, pp. 47\u201355 (2008)"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Vineet, V., Harish, P., Patidar, S., Narayanan, P.J.: Fast minimum spanning tree for large graphs on the gpu. In: HPG, pp. 167\u2013171 (2009)","DOI":"10.1145\/1572769.1572796"},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/978-3-642-23397-5_42","volume-title":"Euro-Par 2011 Parallel Processing","author":"J Jenkins","year":"2011","unstructured":"Jenkins, J., Arkatkar, I., Owens, J.D., Choudhary, A., Samatova, N.F.: Lessons learned from exploring the backtracking paradigm on the GPU. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011, Part II. LNCS, vol. 6853, pp. 425\u2013437. Springer, Heidelberg (2011)"},{"issue":"3","key":"18_CR20","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0255(79)90023-9","volume":"19","author":"JJ McGregor","year":"1979","unstructured":"McGregor, J.J.: Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Information Sciences 19(3), 229\u2013250 (1979)","journal-title":"Information Sciences"},{"issue":"2","key":"18_CR21","first-page":"133","volume":"6","author":"J Lee","year":"2012","unstructured":"Lee, J., Han, W.S., Kasperovics, R., Lee, J.H.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB 6(2), 133\u2013144 (2012)","journal-title":"PVLDB"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"He, B., Fang, W., Luo, Q., Govindaraju, N.K., Wang, T.: Mars: a MapReduce framework on graphics processors. In: PACT, pp. 260\u2013269 (2008)","DOI":"10.1145\/1454115.1454152"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Hong, S., Kim, S.K., Oguntebi, T., Olukotun, K.: Accelerating CUDA graph algorithms at maximum warp. In: PPoPP, pp. 267\u2013276 (2011)","DOI":"10.1145\/2038037.1941590"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: A Recursive Model for Graph Mining. In: SDM, pp. 442\u2013446 (2004)","DOI":"10.1137\/1.9781611972740.43"},{"issue":"6","key":"18_CR25","first-page":"1543","volume":"25","author":"J Zhong","year":"2013","unstructured":"Zhong, J., He, B.: Medusa: Simplified graph processing on GPUs. TPDS 25(6), 1543\u20131552 (2013)","journal-title":"TPDS"},{"key":"18_CR26","unstructured":"Harris, M., Sengupta, S., Owens, J.D.: Gpu gems 3. Parallel Prefix Sum (Scan) with CUDA, pp. 851\u2013876 (2007)"},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Lu, M., He, B., Luo, Q.: Supporting extended precision on graphics processors. In: DaMoN, pp. 19\u201326 (2010)","DOI":"10.1145\/1869389.1869392"}],"container-title":["Lecture Notes in Computer Science","Database Systems for Advanced Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18120-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T11:19:43Z","timestamp":1674213583000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18120-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181196","9783319181202"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18120-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"9 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}