{"id":1034,"date":"2022-04-05T15:50:00","date_gmt":"2022-04-05T14:50:00","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/lotus-locality-optimizing-triangle-counting\/"},"modified":"2024-06-20T16:28:36","modified_gmt":"2024-06-20T15:28:36","slug":"lotus-locality-optimizing-triangle-counting","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/lotus-locality-optimizing-triangle-counting\/","title":{"rendered":"LOTUS: Locality Optimizing Triangle Counting &#8211; PPOPP&#8217;22"},"content":{"rendered":"\n<p><strong><a rel=\"noreferrer noopener\" href=\"https:\/\/ppopp22.sigplan.org\/\" data-type=\"URL\" data-id=\"https:\/\/ppopp22.sigplan.org\/\" target=\"_blank\">27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP 2022)<\/a><\/strong><br>April 2-6, 2022<br>Acceptance Rate: 31%<br><br><strong><a rel=\"noreferrer noopener\" href=\"https:\/\/doi.org\/10.1145\/3503221.3508402\" target=\"_blank\">DOI: 10.1145\/3503221.3508402<\/a><br><\/strong><br><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/LOTUS_TC_Authors_Copy.pdf\"><strong>Authors&#8217; Copy<\/strong> (PDF Format)<\/a><\/p>\n\n\n\n<p>Triangle Counting (TC) is a basic graph algorithm and is widely used in different fields of science, humanities and technology. The great size of real-world graphs with skewed degree distribution is a prohibiting factor in efficient TC.<\/p>\n\n\n\n<p>In this paper, we study the implications of the <strong>power-law degree distribution<\/strong> of graph datasets on <strong>memory utilization in TC<\/strong> and we explain how a great percentage of triangles are formed around a small number of vertices with very great degrees (that are called hubs). <\/p>\n\n\n\n<p>Using these novel observations, we present the <strong>LOTUS<\/strong> algorithm as a structure-aware and  locality optimizing TC that <strong>separates counting triangles formed by hub and non-hub edges<\/strong>. Lotus introduces bespoke TC algorithms and data structures for different edges in order to (i) reduce the size of data structures that are target of random memory accesses, (ii) to optimize cache capacity utilization, (iii) to provide better load balance, and (iv) to avoid fruitless searches.<\/p>\n\n\n\n<p>To provide better CPU utilization, we introduce the <strong>Squared Edge Tiling<\/strong> algorithm that divides a large task into smaller ones when the size of work for each edge in the neighbour-list depends on the index of that edge.<\/p>\n\n\n\n<p>We evaluate the Lotus algorithm on 3 different processor architectures and for real-world graph datasets with up to 162 billion edges that shows <strong>LOTUS provides 2.2-5.5 times speedup<\/strong> in comparison to the previous works.<br><\/p>\n\n\n\n<div class=\"wp-block-jetpack-slideshow aligncenter\" data-effect=\"slide\"><div class=\"wp-block-jetpack-slideshow_container swiper-container\"><ul class=\"wp-block-jetpack-slideshow_swiper-wrapper swiper-wrapper\"><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting\" class=\"wp-block-jetpack-slideshow_image wp-image-1144\" data-id=\"1144\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-01-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting\" class=\"wp-block-jetpack-slideshow_image wp-image-1145\" data-id=\"1145\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-02-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Forward Algorithm\" class=\"wp-block-jetpack-slideshow_image wp-image-1146\" data-id=\"1146\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-03-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Analysis of Forward Algorithm\" class=\"wp-block-jetpack-slideshow_image wp-image-1147\" data-id=\"1147\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-04-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Analysis of Forward Algorithm\" class=\"wp-block-jetpack-slideshow_image wp-image-1148\" data-id=\"1148\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-05-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Analysis of Forward Algorithm\" class=\"wp-block-jetpack-slideshow_image wp-image-1149\" data-id=\"1149\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-06-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Analysis of Forward Algorithm\" class=\"wp-block-jetpack-slideshow_image wp-image-1150\" data-id=\"1150\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-07-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Lotus Graph Structure\" class=\"wp-block-jetpack-slideshow_image wp-image-1166\" data-id=\"1166\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-08-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting -\" class=\"wp-block-jetpack-slideshow_image wp-image-1152\" data-id=\"1152\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-09-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - HHH &amp; HHN\" class=\"wp-block-jetpack-slideshow_image wp-image-1154\" data-id=\"1154\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-10-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - HNN\" class=\"wp-block-jetpack-slideshow_image wp-image-1155\" data-id=\"1155\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-11-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - NNN\" class=\"wp-block-jetpack-slideshow_image wp-image-1157\" data-id=\"1157\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-12-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Evaluation\" class=\"wp-block-jetpack-slideshow_image wp-image-1158\" data-id=\"1158\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-13-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting - Conclusion\" class=\"wp-block-jetpack-slideshow_image wp-image-1159\" data-id=\"1159\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-14-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting -\" class=\"wp-block-jetpack-slideshow_image wp-image-1160\" data-id=\"1160\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-15-1024x576-1.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"LOTUS: Locality Optimizing Triangle Counting -\" class=\"wp-block-jetpack-slideshow_image wp-image-1161\" data-id=\"1161\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Lotus-16-1024x576-1.png\" \/><\/figure><\/li><\/ul><a class=\"wp-block-jetpack-slideshow_button-prev swiper-button-prev swiper-button-white\" role=\"button\"><\/a><a class=\"wp-block-jetpack-slideshow_button-next swiper-button-next swiper-button-white\" role=\"button\"><\/a><a aria-label=\"Pause Slideshow\" class=\"wp-block-jetpack-slideshow_button-pause\" role=\"button\"><\/a><div class=\"wp-block-jetpack-slideshow_pagination swiper-pagination swiper-pagination-white\"><\/div><\/div><\/div>\n\n\n\n<p><strong>Code Availability<\/strong><br>The source-code will be published soon.<\/p>\n\n\n\n<p><strong>BibTex<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>@INPROCEEDINGS{10.1145\/3503221.3508402,\n  author = {Koohi Esfahani, Mohsen and Kilpatrick, Peter and Vandierendonck, Hans},\n  booktitle = {27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP 2022)},  \n  title = {LOTUS: Locality Optimizing Triangle Counting}, \n  year = {2022},\n  numpages = {15},\n  pages={219\u2013233},\n  publisher = {Association for Computing Machinery},\n  address = {New York, NY, USA},\n  doi = {10.1145\/3503221.3508402}\n}<\/code><\/pre>\n\n\n\n<p><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/LaganLighter\"><strong>LaganLighter<\/strong><\/a><\/p>\n\n\n\n<p><strong>Related Posts<\/strong><br><\/p>\n\n\n<ul class=\"wp-block-latest-posts__list has-dates wp-block-latest-posts\"><li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2025\/01\/potra-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/on-optimizing-locality-of-graph-transposition-on-modern-architectures\/\">On Optimizing Locality of Graph Transposition on Modern Architectures<\/a><time datetime=\"2025-01-15T19:32:09+00:00\" class=\"wp-block-latest-posts__post-date\">15 January 2025<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/cones2-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/random-vertex-relabelling-in-laganlighter\/\">Random Vertex Relabelling in LaganLighter<\/a><time datetime=\"2024-08-21T12:37:52+01:00\" class=\"wp-block-latest-posts__post-date\">21 August 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/trees-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/minimum-spanning-forest-of-ms-biographs\/\">Minimum Spanning Forest of MS-BioGraphs<\/a><time datetime=\"2024-08-09T14:11:36+01:00\" class=\"wp-block-latest-posts__post-date\">9 August 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/08\/affinity-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/topology-based-thread-affinity-setting-thread-pinning-in-openmp\/\">Topology-Based Thread Affinity Setting (Thread Pinning) in OpenMP<\/a><time datetime=\"2024-08-03T18:07:31+01:00\" class=\"wp-block-latest-posts__post-date\">3 August 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/02\/loriini-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/paragrapher-integrated-to-laganlighter\/\">ParaGrapher Integrated to LaganLighter<\/a><time datetime=\"2024-02-16T08:29:26+00:00\" class=\"wp-block-latest-posts__post-date\">16 February 2024<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/Squirrel-Dima-Solomin-Unsplash-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/on-designing-structure-aware-high-performance-graph-algorithms-phd-thesis\/\">On Designing Structure-Aware High-Performance Graph Algorithms (PhD Thesis)<\/a><time datetime=\"2022-12-08T10:00:00+00:00\" class=\"wp-block-latest-posts__post-date\">8 December 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/cactus-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/laganlighter-source-code\/\">LaganLighter Source Code<\/a><time datetime=\"2022-11-14T13:17:17+00:00\" class=\"wp-block-latest-posts__post-date\">14 November 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/Mastiff-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/mastiff-structure-aware-minimum-spanning-tree-forest\/\">MASTIFF: Structure-Aware Minimum Spanning Tree\/Forest &#8211; ICS&#8217;22<\/a><time datetime=\"2022-06-28T20:17:30+01:00\" class=\"wp-block-latest-posts__post-date\">28 June 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/White-Stork-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/sapco-sort-optimizing-degree-ordering-for-power-law-graphs\/\">SAPCo Sort: Optimizing Degree-Ordering for Power-Law Graphs &#8211; ISPASS&#8217;22 (Poster)<\/a><time datetime=\"2022-05-23T11:56:43+01:00\" class=\"wp-block-latest-posts__post-date\">23 May 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/lotus-1000x288-1-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/lotus-locality-optimizing-triangle-counting\/\">LOTUS: Locality Optimizing Triangle Counting &#8211; PPOPP&#8217;22<\/a><time datetime=\"2022-04-05T15:50:00+01:00\" class=\"wp-block-latest-posts__post-date\">5 April 2022<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-19-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/locality-analysis-of-graph-reordering-algorithms\/\">Locality Analysis of Graph Reordering Algorithms &#8211; IISWC&#8217;21<\/a><time datetime=\"2021-11-08T08:19:00+00:00\" class=\"wp-block-latest-posts__post-date\">8 November 2021<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/michael-mahood-N_WK99xI9hU-unsplash-2-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/thrifty-label-propagation-fast-connected-components-for-skewed-degree-graphs\/\">Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs &#8211; IEEE CLUSTER&#8217;21<\/a><time datetime=\"2021-09-09T16:34:43+01:00\" class=\"wp-block-latest-posts__post-date\">9 September 2021<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-12-1-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing\/\">Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing &#8211; ICPP&#8217;21<\/a><time datetime=\"2021-08-09T21:07:40+01:00\" class=\"wp-block-latest-posts__post-date\">9 August 2021<\/time><\/li>\n<li><div class=\"wp-block-latest-posts__featured-image alignleft\"><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-11-150x150.jpg\" class=\"attachment-thumbnail size-thumbnail wp-post-image\" alt=\"\" style=\"max-width:75px;max-height:75px;\" \/><\/div><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/how-do-graph-relabeling-algorithms-improve-memory-locality-ispass21\/\">How Do Graph Relabeling Algorithms Improve Memory Locality? ISPASS&#8217;21 (Poster)<\/a><time datetime=\"2021-03-28T08:00:00+01:00\" class=\"wp-block-latest-posts__post-date\">28 March 2021<\/time><\/li>\n<\/ul>","protected":false},"excerpt":{"rendered":"<p>27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP 2022)April 2-6, 2022Acceptance Rate: 31% DOI: 10.1145\/3503221.3508402Authors&#8217; Copy (PDF Format) Triangle Counting (TC) is a basic graph algorithm and is widely used in different fields of science, humanities and technology. The great size of real-world graphs with skewed degree distribution is a [&hellip;]<\/p>\n","protected":false},"author":1315,"featured_media":1630,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[40],"tags":[34,43,48,35,38,49,39,26,44,50],"class_list":{"0":"post-1034","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-laganlighter","8":"tag-algorithm-design-and-engineering","9":"tag-algorithm-engineering","10":"tag-graph-mining","11":"tag-graph-processing","12":"tag-high-performance-computing","13":"tag-k-clique","14":"tag-laganlighter","15":"tag-locality","16":"tag-structure-aware-algorithms","17":"tag-triangle-counting","18":"czr-hentry"},"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/lotus-1000x288-1.jpg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1034","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/users\/1315"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=1034"}],"version-history":[{"count":1,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1034\/revisions"}],"predecessor-version":[{"id":3145,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1034\/revisions\/3145"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/1630"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=1034"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=1034"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=1034"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}