{"id":633,"date":"2021-09-09T16:34:43","date_gmt":"2021-09-09T15:34:43","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/thrifty-label-propagation-fast-connected-components-for-skewed-degree-graphs\/"},"modified":"2024-06-20T16:28:36","modified_gmt":"2024-06-20T15:28:36","slug":"thrifty-label-propagation-fast-connected-components-for-skewed-degree-graphs","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/thrifty-label-propagation-fast-connected-components-for-skewed-degree-graphs\/","title":{"rendered":"Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs &#8211; IEEE CLUSTER&#8217;21"},"content":{"rendered":"<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><a href=\"https:\/\/clustercomp.org\/2021\/\"><img decoding=\"async\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/ieee-cluster-21.png\" alt=\"IEEE CLUSTER 2021\" class=\"wp-image-766\" \/><\/a><\/figure>\n<\/div>\n\n\n<p><strong><a rel=\"noreferrer noopener\" href=\"https:\/\/clustercomp.org\/2021\/\" target=\"_blank\">IEEE CLUSTER 2021<br><\/a>7-10 September<\/strong><br>Acceptance rate: 29.4%<br><br><a rel=\"noreferrer noopener\" href=\"https:\/\/doi.org\/10.1109\/Cluster48925.2021.00042\" target=\"_blank\"><strong>DOI<\/strong>: 10.1109\/Cluster48925.2021.00042<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/ieeexplore.ieee.org\/document\/9555986\" data-type=\"URL\" data-id=\"https:\/\/ieeexplore.ieee.org\/document\/9555986\" target=\"_blank\">IEEE Xplore<\/a><br><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty_AuthorCopy.pdf\"><strong>PDF Version<\/strong> (Authors&#8217; Copy)<\/a><br><\/p>\n\n\n\n<p>Thrifty introduces four optimization techniques to Label Propagation Connected Components:<\/p>\n\n\n\n<p>1)<strong> Unified Labels Array<\/strong> accelerates label propagation by allowing the latest label of each vertex to be read in processing other vertices.<br><br>2) <strong>Zero Convergence<\/strong> optimizes work-efficiency in the pull iterations of Label Propagation by skipping converged vertices.<\/p>\n\n\n\n<p>3) <strong>Zero Planting<\/strong> selects the best start propagating point and increases the convergence rate and removes pull iterations that are required for the lowest label to reach the core of graph.<\/p>\n\n\n\n<p>4) <strong>Initial Push<\/strong> technique makes the first iteration work efficient by skipping processing edges of vertices that probability of convergence is very small.<\/p>\n\n\n\n<p>Based on these optimizations, Thrifty provides <strong>1.4\u2715 speedup to <a style=\"color:black\" rel=\"noopener\" href=\"https:\/\/ieeexplore.ieee.org\/document\/8425156\" target=\"_blank\">Afforest<\/a><\/strong>, 6.6\u2715 to <a style=\"font-weight:normal;color:black\" rel=\"noopener\" href=\"https:\/\/arxiv.org\/abs\/1612.01514\" target=\"_blank\">Jayanti-Tarjan<\/a>, 14.3\u2715 to BFS-CC, and 25.0\u2715 to Direction Optimizing Label Propagation. <\/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=\"Thrifty Label Propagation: Fast Connected Components For Skewed Degree Graphs\" class=\"wp-block-jetpack-slideshow_image wp-image-849\" data-id=\"849\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-01.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Outline\" class=\"wp-block-jetpack-slideshow_image wp-image-850\" data-id=\"850\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-02.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Background\" class=\"wp-block-jetpack-slideshow_image wp-image-851\" data-id=\"851\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-03.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Background\" class=\"wp-block-jetpack-slideshow_image wp-image-852\" data-id=\"852\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-04.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Background\" class=\"wp-block-jetpack-slideshow_image wp-image-853\" data-id=\"853\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-05.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation\" class=\"wp-block-jetpack-slideshow_image wp-image-854\" data-id=\"854\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-06.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Unified Labels Array\" class=\"wp-block-jetpack-slideshow_image wp-image-855\" data-id=\"855\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-07.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Unified Labels Array\" class=\"wp-block-jetpack-slideshow_image wp-image-856\" data-id=\"856\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-08.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Zero Convergence\" class=\"wp-block-jetpack-slideshow_image wp-image-857\" data-id=\"857\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-09.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Zero Convergence\" class=\"wp-block-jetpack-slideshow_image wp-image-858\" data-id=\"858\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-10.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Zero Planting\" class=\"wp-block-jetpack-slideshow_image wp-image-859\" data-id=\"859\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-11.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation: Zero Planting\" class=\"wp-block-jetpack-slideshow_image wp-image-860\" data-id=\"860\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-12.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  Initial Push\" class=\"wp-block-jetpack-slideshow_image wp-image-861\" data-id=\"861\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-13.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  Evaluation\" class=\"wp-block-jetpack-slideshow_image wp-image-862\" data-id=\"862\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-14.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  Evaluation\" class=\"wp-block-jetpack-slideshow_image wp-image-863\" data-id=\"863\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-15.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  Evaluation\" class=\"wp-block-jetpack-slideshow_image wp-image-864\" data-id=\"864\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-16.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  Conclusion\" class=\"wp-block-jetpack-slideshow_image wp-image-865\" data-id=\"865\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-17.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  Thanks\" class=\"wp-block-jetpack-slideshow_image wp-image-866\" data-id=\"866\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-18.png\" \/><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"Thrifty Label Propagation:  A Gift from QUB\" class=\"wp-block-jetpack-slideshow_image wp-image-867\" data-id=\"867\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-19.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><br><strong>Code Availability<\/strong><br>The source-code of Thrifty is available on<a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/LaganLighter-Source-Code\/\"> <strong>LaganLighter Repository<\/strong> (<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/github.com\/DIPSA-QUB\/LaganLighter\/blob\/main\/alg2_thrifty.c\" target=\"_blank\">alg2_thrifty.c<\/a> and <a rel=\"noreferrer noopener\" href=\"https:\/\/github.com\/DIPSA-QUB\/LaganLighter\/blob\/main\/cc.c\" target=\"_blank\">cc.c<\/a> files). A sample execution of this source code for \u201cTwitter-MPI\u201d graph is shown in the following:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-Label-Propagation-Connected-Components-LaganLighter-Run.png\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/Thrifty-Label-Propagation-Connected-Components-LaganLighter-Run-1024x510.png\" alt=\"\" class=\"wp-image-1452\" \/><\/a><\/figure>\n\n\n\n<p> <br><strong>Bibtex<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>@INPROCEEDINGS{10.1109\/Cluster48925.2021.00042,\n  author={Koohi Esfahani, Mohsen and Kilpatrick, Peter and Vandierendonck, Hans},\n  booktitle={2021 IEEE International Conference on Cluster Computing (CLUSTER)}, \n  title={Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs}, \n  year={2021},\n  volume={},\n  number={},\n  pages={226-237},\n  publisher={IEEE Computer Society},\n  doi={10.1109\/Cluster48925.2021.00042}\n}\n<\/code><\/pre>\n\n\n\n<p><strong>Related Posts<\/strong><\/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>IEEE CLUSTER 20217-10 SeptemberAcceptance rate: 29.4% DOI: 10.1109\/Cluster48925.2021.00042IEEE XplorePDF Version (Authors&#8217; Copy) Thrifty introduces four optimization techniques to Label Propagation Connected Components: 1) Unified Labels Array accelerates label propagation by allowing the latest label of each vertex to be read in processing other vertices. 2) Zero Convergence optimizes work-efficiency in the pull iterations of Label [&hellip;]<\/p>\n","protected":false},"author":1315,"featured_media":1632,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[40],"tags":[34,43,45,35,38,46,39,29,44],"class_list":{"0":"post-633","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-connectedcomponents","11":"tag-graph-processing","12":"tag-high-performance-computing","13":"tag-labelpropagation","14":"tag-laganlighter","15":"tag-pushpull","16":"tag-structure-aware-algorithms","17":"czr-hentry"},"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/michael-mahood-N_WK99xI9hU-unsplash-2.jpg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/633","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=633"}],"version-history":[{"count":1,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/633\/revisions"}],"predecessor-version":[{"id":3146,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/633\/revisions\/3146"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/1632"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}