{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:12Z","timestamp":1750220592196,"version":"3.41.0"},"reference-count":93,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Laboratory","award":["DEAC52-07NA27344 (LLNL-JRNL-817625)"],"award-info":[{"award-number":["DEAC52-07NA27344 (LLNL-JRNL-817625)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>Pattern matching is a fundamental tool for answering complex graph queries. Unfortunately, existing solutions have limited capabilities: They do not scale to process large graphs and\/or support only a restricted set of search templates or usage scenarios. Moreover, the algorithms at the core of the existing techniques are not suitable for today\u2019s graph processing infrastructures relying on horizontal scalability and shared-nothing clusters, as most of these algorithms are inherently sequential and difficult to parallelize.<\/jats:p>\n          <jats:p>\n            We present an algorithmic pipeline that bases pattern matching on\n            <jats:italic>constraint checking<\/jats:italic>\n            . The key intuition is that each vertex and edge participating in a match has to meet a set of constraints implicitly specified by the search template. These constraints can be verified independently and typically are less expensive to compute than searching the full template. The pipeline we propose generates these constraints and iterates over them to eliminate all the vertices and edges that\n            <jats:italic>do not<\/jats:italic>\n            participate in any match, thus reducing the background graph to a subgraph that is the union of all template matches\u2014the\n            <jats:italic>complete set<\/jats:italic>\n            of all vertices and edges that participate in at least one match. Additional analysis can be performed on this annotated, reduced graph, such as full match enumeration, match counting, or computing vertex\/edge centrality. Furthermore, a\n            <jats:italic>vertex-centric<\/jats:italic>\n            formulation for constraint checking algorithms exists, and this makes it possible to harness existing high-performance, vertex-centric graph processing frameworks.\n          <\/jats:p>\n          <jats:p>This technique (i) enables highly scalable pattern matching in metadata (labeled) graphs; (ii) supports arbitrary patterns with 100% precision; (iii) enables tradeoffs between precision and time-to-solution, while always selects all vertices and edges that participate in matches, thus offering 100% recall; and (iv) supports a set of popular data analytics scenarios. We implement our approach on top of HavoqGT, an open-source asynchronous graph processing framework, and demonstrate its advantages through strong and weak scaling experiments on massive scale real-world (up to 257 billion edges) and synthetic (up to 4.4 trillion edges) labeled graphs, respectively, and at scales (1,024 nodes \/ 36,864 cores), orders of magnitude larger than used in the past for similar problems.<\/jats:p>\n          <jats:p>\n            This article serves two purposes: First, it synthesises the knowledge accumulated during a long-term project [Reza et\u00a0al. 2017, 2018; Tripoul et\u00a0al. 2018]. Second, it presents new system features, usage scenarios, optimizations, and comparisons with related work that strengthen the confidence that pattern matching based on iterative pruning via constraint checking is an effective and scalable approach in practice. The new contributions include the following: (i) We demonstrate the ability of the constraint checking approach to efficiently support two additional search scenarios that often emerge in practice,\n            <jats:italic>interactive incremental search<\/jats:italic>\n            and\n            <jats:italic>exploratory search<\/jats:italic>\n            . (ii) We empirically compare our solution with two additional state-of-the-art systems, Arabsque [Teixeira et\u00a0al. 2015] and TriAD [Gurajada et\u00a0al. 2014]. (iii) We show the ability of our solution to accommodate a more diverse range of datasets with varying properties, e.g., scale, skewness, label distribution, and match frequency. (iv) We introduce or extend a number of system features (e.g., work aggregation, load balancing, and the ability to cap the generated traffic) and design optimizations and demonstrate their advantages with respect to improving performance and scalability. (v) We present bottleneck analysis and insights into artifacts that influence performance. (vi) We present a theoretical complexity argument that motivates the performance gains we observe.\n          <\/jats:p>","DOI":"10.1145\/3434391","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T14:45:42Z","timestamp":1609771542000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Scalable Pattern Matching in Metadata Graphs via Constraint Checking"],"prefix":"10.1145","volume":"8","author":[{"given":"Tahsin","family":"Reza","sequence":"first","affiliation":[{"name":"University of British Columbia, Vancouver, BC Canada"}]},{"given":"Hassan","family":"Halawa","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, BC Canada"}]},{"given":"Matei","family":"Ripeanu","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, BC Canada"}]},{"given":"Geoffrey","family":"Sanders","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, CA USA"}]},{"given":"Roger A.","family":"Pearce","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, CA USA"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151109"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654078"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium. 1--14","author":"Berry J. W.","year":"2007","unstructured":"J. W. Berry , B. Hendrickson , S. Kahan , and P. Konecny . 2007. Software and algorithms for graph queries on multithreaded architectures . In Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium. 1--14 . DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2007 .370685 J. W. Berry, B. Hendrickson, S. Kahan, and P. Konecny. 2007. Software and algorithms for graph queries on multithreaded architectures. In Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium. 1--14. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2007.370685"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"volume-title":"Proceedings of the 13th International Conference on World Wide Web (WWW\u201904)","author":"Boldi P.","key":"e_1_2_1_8_1","unstructured":"P. Boldi and S. Vigna . 2004. The webgraph framework I: Compression techniques . In Proceedings of the 13th International Conference on World Wide Web (WWW\u201904) . ACM, New York, NY, 595--602. DOI:https:\/\/doi.org\/10.1145\/988672.988752 P. Boldi and S. Vigna. 2004. The webgraph framework I: Compression techniques. In Proceedings of the 13th International Conference on World Wide Web (WWW\u201904). ACM, New York, NY, 595--602. DOI:https:\/\/doi.org\/10.1145\/988672.988752"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(83)90033-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2015.74"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916)","author":"Chakaravarthy V. T.","year":"2016","unstructured":"V. T. Chakaravarthy , M. Kapralov , P. Murali , F. Petrini , X. Que , Y. Sabharwal , and B. Schieber . 2016. Subgraph counting: Color coding beyond trees . In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916) . 2--11. DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2016 .122 V. T. Chakaravarthy, M. Kapralov, P. Murali, F. Petrini, X. Que, Y. Sabharwal, and B. Schieber. 2016. Subgraph counting: Color coding beyond trees. In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916). 2--11. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2016.122"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"volume-title":"Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW\u201916)","author":"Chavarr\u00eda-Miranda D.","key":"e_1_2_1_13_1","unstructured":"D. Chavarr\u00eda-Miranda , V. G. Castellana , A. Morari , D. Haglin , and J. Feo . 2016. GraQL: A query language for high-performance attributed graph databases . In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW\u201916) . 1453--1462. D. Chavarr\u00eda-Miranda, V. G. Castellana, A. Morari, D. Haglin, and J. Feo. 2016. GraQL: A query language for high-performance attributed graph databases. In Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW\u201916). 1453--1462."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2015 18th International Conference on Extending Database Technology (EDBT\u201915)","author":"Choudhury Sutanay","year":"2015","unstructured":"Sutanay Choudhury , Lawrence Holder , George Chin , Khushbu Agarwal , and John Feo . 2015 . A selectivity based approach to continuous pattern detection in streaming graphs . In Proceedings of the 2015 18th International Conference on Extending Database Technology (EDBT\u201915) . Sutanay Choudhury, Lawrence Holder, George Chin, Khushbu Agarwal, and John Feo. 2015. A selectivity based approach to continuous pattern detection in streaming graphs. In Proceedings of the 2015 18th International Conference on Extending Database Technology (EDBT\u201915)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960416"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691601"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816681"},{"key":"e_1_2_1_25_1","unstructured":"Giraph. 2016. Giraph. Retrieved from http:\/\/giraph.apache.org.  Giraph. 2016. Giraph. Retrieved from http:\/\/giraph.apache.org."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez , Yucheng Low , Haijie Gu , Danny Bickson , and Carlos Guestrin . 2012 . PowerGraph: Distributed graph-parallel computation on natural graphs . In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912) . USENIX Association, Berkeley, CA, 17--30. http:\/\/dl.acm.org\/citation.cfm?id=2387880.2387883 Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912). USENIX Association, Berkeley, CA, 17--30. http:\/\/dl.acm.org\/citation.cfm?id=2387880.2387883"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914)","author":"Gonzalez Joseph E.","year":"2014","unstructured":"Joseph E. Gonzalez , Reynold S. Xin , Ankur Dave , Daniel Crankshaw , Michael J. Franklin , and Ion Stoica . 2014 . GraphX: Graph processing in a distributed dataflow framework . In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914) . USENIX Association, Berkeley, CA, 599--613. http:\/\/dl.acm.org\/citation.cfm?id=2685048.2685096 Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014. GraphX: Graph processing in a distributed dataflow framework. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914). USENIX Association, Berkeley, CA, 599--613. http:\/\/dl.acm.org\/citation.cfm?id=2685048.2685096"},{"key":"e_1_2_1_28_1","unstructured":"Graph 500. 2016. Graph 500 Benchmark. Retrieved from http:\/\/www. graph500.org.  Graph 500. 2016. Graph 500 Benchmark. Retrieved from http:\/\/www. graph500.org."},{"key":"e_1_2_1_29_1","unstructured":"GraphFrames. 2017. GraphFrames. Retrieved from http:\/\/graphframes.github.io.  GraphFrames. 2017. GraphFrames. Retrieved from http:\/\/graphframes.github.io."},{"volume-title":"Proceedings of the 2018 IEEE High Performance extreme Computing Conference (HPEC\u201918)","author":"Green O.","key":"e_1_2_1_30_1","unstructured":"O. Green , J. Fox , A. Watkins , A. Tripathy , K. Gabert , E. Kim , X. An , K. Aatish , and D. A. Bader . 2018. Logarithmic radix binning and vectorized triangle counting . In Proceedings of the 2018 IEEE High Performance extreme Computing Conference (HPEC\u201918) . 1--7. O. Green, J. Fox, A. Watkins, A. Tripathy, K. Gabert, E. Kim, X. An, K. Aatish, and D. A. Bader. 2018. Logarithmic radix binning and vectorized triangle counting. In Proceedings of the 2018 IEEE High Performance extreme Computing Conference (HPEC\u201918). 1--7."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610511"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Ninth European Conference on Computer Systems (EuroSys\u201914)","author":"Han Wentao","year":"2014","unstructured":"Wentao Han , Youshan Miao , Kaiwei Li , Ming Wu , Fan Yang , Lidong Zhou , Vijayan Prabhakaran , Wenguang Chen , and Enhong Chen . 2014 . Chronos: A graph engine for temporal graph analysis . In Proceedings of the Ninth European Conference on Computer Systems (EuroSys\u201914) . ACM, New York, NY, Article 1, 14 pages. DOI:https:\/\/doi.org\/10.1145\/2592798.2592799 Wentao Han, Youshan Miao, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Wenguang Chen, and Enhong Chen. 2014. Chronos: A graph engine for temporal graph analysis. In Proceedings of the Ninth European Conference on Computer Systems (EuroSys\u201914). ACM, New York, NY, Article 1, 14 pages. DOI:https:\/\/doi.org\/10.1145\/2592798.2592799"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_36_1","unstructured":"HavoqGT. 2016. HavoqGT. Retrieved from http:\/\/software.llnl.gov\/havoqgt.  HavoqGT. 2016. HavoqGT. Retrieved from http:\/\/software.llnl.gov\/havoqgt."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906)","author":"He Huahai","year":"2006","unstructured":"Huahai He and A. K. Singh . 2006. Closure-Tree: An index structure for graph queries . In Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906) . 38--38. DOI:https:\/\/doi.org\/10.1109\/ICDE. 2006 .37 Huahai He and A. K. Singh. 2006. Closure-Tree: An index structure for graph queries. In Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906). 38--38. DOI:https:\/\/doi.org\/10.1109\/ICDE.2006.37"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339723"},{"volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS\u201995)","author":"Henzinger M. R.","key":"e_1_2_1_39_1","unstructured":"M. R. Henzinger , T. A. Henzinger , and P. W. Kopke . 1995. Computing simulations on finite and infinite graphs . In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS\u201995) . IEEE Computer Society, Los Alamitos, CA, 453. M. R. Henzinger, T. A. Henzinger, and P. W. Kopke. 1995. Computing simulations on finite and infinite graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS\u201995). IEEE Computer Society, Los Alamitos, CA, 453."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807620"},{"key":"e_1_2_1_41_1","unstructured":"IMDb. 2016. IMDb Public Data. Retrieved from http:\/\/www.imdb.com\/interfaces.  IMDb. 2016. IMDb Public Data. Retrieved from http:\/\/www.imdb.com\/interfaces."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI'18)","author":"Iyer Anand Padmanabha","year":"2018","unstructured":"Anand Padmanabha Iyer , Zaoxing Liu , Xin Jin , Shivaram Venkataraman , Vladimir Braverman , and Ion Stoica . 2018 . ASAP: Fast, approximate graph pattern mining at scale . In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI'18) . USENIX Association, Berekely, CA, 745--761. Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. 2018. ASAP: Fast, approximate graph pattern mining at scale. In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI'18). USENIX Association, Berekely, CA, 745--761."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2907294.2907312"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_45_1","unstructured":"BGL. 2017. The Boost Graph Library (BGL). Retrieved from http:\/\/www.boost.org\/doc\/libs\/master\/libs\/graph\/doc\/index.html.  BGL. 2017. The Boost Graph Library (BGL). Retrieved from http:\/\/www.boost.org\/doc\/libs\/master\/libs\/graph\/doc\/index.html."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.190"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557083"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.03.007"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2591038"},{"key":"e_1_2_1_50_1","unstructured":"Lustre. 2016. The Lustre File System. Retrieved from http:\/\/lustre.org.  Lustre. 2016. The Lustre File System. Retrieved from http:\/\/lustre.org."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187963"},{"volume-title":"Proceedings of the 2017 IEEE 24th International Conference on High Performance Computing (HiPC\u201917)","author":"Makkar D.","key":"e_1_2_1_52_1","unstructured":"D. Makkar , D. A. Bader , and O. Green . 2017. Exact and parallel triangle counting in dynamic graphs . In Proceedings of the 2017 IEEE 24th International Conference on High Performance Computing (HiPC\u201917) . 2--12. D. Makkar, D. A. Bader, and O. Green. 2017. Exact and parallel triangle counting in dynamic graphs. In Proceedings of the 2017 IEEE 24th International Conference on High Performance Computing (HiPC\u201917). 2--12."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/028\/14"},{"key":"e_1_2_1_56_1","volume-title":"Gems: Graph Database Engine for Multithreaded Systems. 139--156.","author":"Morari Alessandro","year":"2015","unstructured":"Alessandro Morari , Vito Castellana , O. Villa , J. Weaver , G. Williams , David Haglin , Antonino Tumeo , and John Feo . 2015 . Gems: Graph Database Engine for Multithreaded Systems. 139--156. Alessandro Morari, Vito Castellana, O. Villa, J. Weaver, G. Williams, David Haglin, Antonino Tumeo, and John Feo. 2015. Gems: Graph Database Engine for Multithreaded Systems. 139--156."},{"volume-title":"Proceedings of the 2015 IEEE International Conference on Cluster Computing. 250--253","author":"Morari A.","key":"e_1_2_1_57_1","unstructured":"A. Morari , J. Weaver , O. Villa , D. Haglin , A. Tumeo , V. G. Castellana , and J. Feo . 2015. High-performance, distributed dictionary encoding of RDF datasets . In Proceedings of the 2015 IEEE International Conference on Cluster Computing. 250--253 . A. Morari, J. Weaver, O. Villa, D. Haglin, A. Tumeo, V. G. Castellana, and J. Feo. 2015. High-performance, distributed dictionary encoding of RDF datasets. In Proceedings of the 2015 IEEE International Conference on Cluster Computing. 250--253."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS\u201913)","author":"Pearce Roger","year":"2013","unstructured":"Roger Pearce , Maya Gokhale , and Nancy M. Amato . 2013. Scaling techniques for massive scale-free graphs in distributed (external) memory . In Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS\u201913) . IEEE Computer Society, Washington, DC, 825--836. DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2013 .72 Roger Pearce, Maya Gokhale, and Nancy M. Amato. 2013. Scaling techniques for massive scale-free graphs in distributed (external) memory. In Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS\u201913). IEEE Computer Society, Washington, DC, 825--836. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2013.72"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201914)","author":"Pearce Roger","year":"2014","unstructured":"Roger Pearce , Maya Gokhale , and Nancy M. Amato . 2014. Faster parallel traversal of scale free graphs at extreme scale with vertex delegates . In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201914) . IEEE Press, Piscataway, NJ, 549--559. DOI:https:\/\/doi.org\/10.1109\/SC. 2014 .50 Roger Pearce, Maya Gokhale, and Nancy M. Amato. 2014. Faster parallel traversal of scale free graphs at extreme scale with vertex delegates. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201914). IEEE Press, Piscataway, NJ, 549--559. DOI:https:\/\/doi.org\/10.1109\/SC.2014.50"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.10.005"},{"key":"e_1_2_1_62_1","unstructured":"Quartz. 2017. Quartz. Retrieved from https:\/\/hpc.llnl.gov\/hardware\/platforms\/Quartz.  Quartz. 2017. Quartz. Retrieved from https:\/\/hpc.llnl.gov\/hardware\/platforms\/Quartz."},{"key":"e_1_2_1_63_1","unstructured":"RDF. 2017. LargeTripleStores. Retrieved from https:\/\/www.w3.org\/wiki\/LargeTripleStores.  RDF. 2017. LargeTripleStores. Retrieved from https:\/\/www.w3.org\/wiki\/LargeTripleStores."},{"key":"e_1_2_1_64_1","unstructured":"Reddit. 2017. Reddit Public Data. Retrieved from https:\/\/github.com\/dewarim\/reddit-data-tools.  Reddit. 2017. Reddit Public Data. Retrieved from https:\/\/github.com\/dewarim\/reddit-data-tools."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2017.85"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380566"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3398682.3399166"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00024"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0303-4"},{"key":"e_1_2_1_70_1","unstructured":"Oliver Lehmberg Robert Meusel Christian Bizer. 2016. Web Data Commons\u2014Hyperlink Graphs. Retrieved from http:\/\/webdatacommons.org\/hyperlinkgraph\/index.html.  Oliver Lehmberg Robert Meusel Christian Bizer. 2016. Web Data Commons\u2014Hyperlink Graphs. Retrieved from http:\/\/webdatacommons.org\/hyperlinkgraph\/index.html."},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201915)","author":"Ryan","key":"e_1_2_1_71_1","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization . In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201915) . Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201915)."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078447.3078454"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014945"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127479.3131625"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_76_1","volume-title":"Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201914)","author":"Slota G. M.","year":"2014","unstructured":"G. M. Slota and K. Madduri . 2014. Complex network analysis using parallel approximate motif counting . In Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201914) . IEEE, 405--414. DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2014 .50 G. M. Slota and K. Madduri. 2014. Complex network analysis using parallel approximate motif counting. In Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201914). IEEE, 405--414. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2014.50"},{"key":"e_1_2_1_77_1","unstructured":"Spark. 2017. Spark. Retrieved from https:\/\/spark.apache.org.  Spark. 2017. Spark. Retrieved from https:\/\/spark.apache.org."},{"key":"e_1_2_1_78_1","unstructured":"SPARQL1.0. 2017. SPARQL 1.0. Retrieved from https:\/\/www.w3.org\/TR\/rdf-sparql-query.  SPARQL1.0. 2017. SPARQL 1.0. Retrieved from https:\/\/www.w3.org\/TR\/rdf-sparql-query."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281271"},{"key":"e_1_2_1_84_1","volume-title":"Proceedings of the 2018 IEEE\/ACM 8th Workshop on Irregular Applications: Architectures and Algorithms (IA3\u201918)","author":"Tripoul N.","year":"2018","unstructured":"N. Tripoul , H. Halawa , T. Reza , G. Sanders , R. Pearce , and M. Ripeanu . 2018. There are trillions of little forks in the road. choose wisely! Estimating the cost and likelihood of success of constrained walks to optimize a graph pruning pipeline . In Proceedings of the 2018 IEEE\/ACM 8th Workshop on Irregular Applications: Architectures and Algorithms (IA3\u201918) . 20--27. DOI:https:\/\/doi.org\/10.1109\/IA3. 2018 .00010 N. Tripoul, H. Halawa, T. Reza, G. Sanders, R. Pearce, and M. Ripeanu. 2018. There are trillions of little forks in the road. choose wisely! Estimating the cost and likelihood of success of constrained walks to optimize a graph pruning pipeline. In Proceedings of the 2018 IEEE\/ACM 8th Workshop on Irregular Applications: Architectures and Algorithms (IA3\u201918). 20--27. DOI:https:\/\/doi.org\/10.1109\/IA3.2018.00010"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093337.3037748"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMAS.2000.858469"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9940-4"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0381-6"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920843"},{"key":"e_1_2_1_91_1","volume-title":"Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium. 390--401","author":"Zhao Z.","year":"2012","unstructured":"Z. Zhao , G. Wang , A. R. Butt , M. Khan , V. S. A. Kumar , and M. V. Marathe . 2012. SAHAD: Subgraph analysis in massive networks using hadoop . In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium. 390--401 . DOI:https:\/\/doi.org\/10.1109\/IPDPS. 2012 .44 Z. Zhao, G. Wang, A. R. Butt, M. Khan, V. S. A. Kumar, and M. V. Marathe. 2012. SAHAD: Subgraph analysis in massive networks using hadoop. In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium. 390--401. DOI:https:\/\/doi.org\/10.1109\/IPDPS.2012.44"},{"volume-title":"Simplification of Networks by Edge Pruning","author":"Zhou Fang","key":"e_1_2_1_92_1","unstructured":"Fang Zhou , S\u00e9bastien Mahler , and Hannu Toivonen . 2012. Simplification of Networks by Edge Pruning . Springer , Berlin , 179--198. DOI:https:\/\/doi.org\/10.1007\/978-3-642-31830-6_13 Fang Zhou, S\u00e9bastien Mahler, and Hannu Toivonen. 2012. Simplification of Networks by Edge Pruning. Springer, Berlin, 179--198. DOI:https:\/\/doi.org\/10.1007\/978-3-642-31830-6_13"},{"key":"e_1_2_1_93_1","volume-title":"Proc. VLDB Endow. 4, 11 (8","author":"Zhu Feida","year":"2011","unstructured":"Feida Zhu , Qiang Qu , David Lo , Xifeng Yan , Jiawei Han , and Philip S. Yu . 2011. Mining top-K large structural patterns in a massive network . Proc. VLDB Endow. 4, 11 (8 2011 ), 807--818. Feida Zhu, Qiang Qu, David Lo, Xifeng Yan, Jiawei Han, and Philip S. Yu. 2011. Mining top-K large structural patterns in a massive network. Proc. VLDB Endow. 4, 11 (8 2011), 807--818."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434391","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:47Z","timestamp":1750195907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":93,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3434391"],"URL":"https:\/\/doi.org\/10.1145\/3434391","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}