{"id":1622,"date":"2021-03-28T08:00:00","date_gmt":"2021-03-28T07:00:00","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/how-do-graph-relabeling-algorithms-improve-memory-locality-ispass21\/"},"modified":"2024-06-20T16:28:36","modified_gmt":"2024-06-20T15:28:36","slug":"how-do-graph-relabeling-algorithms-improve-memory-locality-ispass21","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/how-do-graph-relabeling-algorithms-improve-memory-locality-ispass21\/","title":{"rendered":"How Do Graph Relabeling Algorithms Improve Memory Locality? ISPASS&#8217;21 (Poster)"},"content":{"rendered":"\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/doi.org\/10.1109\/ISPASS51385.2021.00023\" target=\"_blank\"><strong>IEEE Xplore <\/strong>(<strong>DOI: <\/strong>10.1109\/ISPASS51385.2021.00023)<\/a><br><strong><a rel=\"noreferrer noopener\" href=\"https:\/\/www.ispass.org\/ispass2021\/\" target=\"_blank\">ISPASS-2021<\/a><\/strong><br><strong><a rel=\"noreferrer noopener\" href=\"https:\/\/ieeexplore.ieee.org\/xpl\/conhome\/9408088\/proceeding\" target=\"_blank\">2021 IEEE International Symposium on Performance Analysis of Systems and Software<\/a><\/strong><br><strong>March 28-30, 2021<\/strong><\/p>\n\n\n\n<p><strong><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/how-do-graph-relabeling-algorithms-improve-memory-locality-ispass21.pdf\">Authors&#8217; Copy (PDF Format)<\/a><\/strong><\/p>\n\n\n\n<p class=\"has-medium-font-size\">For a complete version of this article, please refer to <strong><a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/locality-analysis-of-graph-reordering-algorithms\/\">Locality Analysis of Graph Reordering Algorithms<\/a><\/strong> and also Chapter 3 of the<strong> <a 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 thesis<\/a>.<\/strong><br><\/p>\n\n\n\n<p class=\"has-text-align-justify\">Relabeling (reordering) algorithms aim to improve the poor memory locality of graph processing by changing the order of vertices. This paper analyses the functionality of three state-of-the-art relabeling algorithms: <strong><a style=\"color:black\" rel=\"noreferrer noopener\" href=\"https:\/\/ieeexplore.ieee.org\/document\/6807798\" target=\"_blank\">SlashBurn<\/a><\/strong>, <strong><a style=\"color:black\" rel=\"noreferrer noopener\" href=\"https:\/\/dl.acm.org\/doi\/10.1145\/2882903.2915220\" target=\"_blank\">GOrder<\/a><\/strong>, and <strong><a style=\"color:black\" rel=\"noreferrer noopener\" href=\"https:\/\/ieeexplore.ieee.org\/document\/7515998\" target=\"_blank\">Rabbit-Order<\/a><\/strong> for real-world graphs.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">We use a number of techniques to explain how locality is affected by relabeling algorithms and how locality of different datasets (like social networks and web graphs) is enhanced by relabeling algorithms.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">We use last level cache simulation to study miss rate degree distribution. We also use the degree distribution of Giant Connected Component (GCC) in SlashBurn iterations to see if real-world graphs follow the assumption that &#8220;power-law graphs are created\/destroyed recursively&#8221; [<a style=\"color:black\" rel=\"noreferrer noopener\" href=\"https:\/\/ieeexplore.ieee.org\/document\/6807798\" target=\"_blank\">SlashBurn<\/a>]. We represent <strong>SlashBurn++<\/strong> as an enhanced version of SlashBurn with lower preprocessing time and better locality. <\/p>\n\n\n\n<p class=\"has-text-align-justify\">Using cache simulation, we count the number of misses for accessing vertices data of high-degree vertices. This helps to explain how GOrder provides better <strong>temporal locality<\/strong> by managing cache space. <strong>Average ID Distance (AID)<\/strong> is a spatial locality metric introduced in this paper to explain how clustering relabeling algorithms like Rabbit-Order provide better <strong>spatial locality<\/strong>. <\/p>\n\n\n\n<p class=\"has-text-align-justify\">This paper also investigates why push and pull traversals of different datasets show different performances by introducing <strong>Push Locality<\/strong> and <strong>Pull Locality<\/strong>.  <\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\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=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-415\" data-id=\"415\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-01.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">How Do Graph Relabeling Algorithms  Improve Memory  Locality?<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-486\" data-id=\"486\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-02-6.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Outline<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-417\" data-id=\"417\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-03.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">What is Locality?<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-418\" data-id=\"418\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-04.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">What is Graph Relabeling (Reordering) ?<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-419\" data-id=\"419\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-05.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Why is Relabeling Important for Graph Processing?<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-420\" data-id=\"420\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-06.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Why is Relabeling Important for Graph Processing?<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-421\" data-id=\"421\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-07.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Graph Traversals<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-422\" data-id=\"422\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-08.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Performance of Relabeling Algorithms<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-423\" data-id=\"423\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-09.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Performance of Relabeling Algorithms<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-424\" data-id=\"424\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-10.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Performance of Relabeling Algorithms<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-425\" data-id=\"425\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-11.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">SlashBurn: Community Detection for Power-law Graphs<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-426\" data-id=\"426\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-12.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">SlashBurn: Community Detection for Power-law Graphs<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-427\" data-id=\"427\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-13.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">SlashBurn++<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-428\" data-id=\"428\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-14.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">GOrder: Cache Simulation for Pull Traversal<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-429\" data-id=\"429\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-15.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">GOrder: Cache Simulation for Pull Traversal<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-430\" data-id=\"430\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-16.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Rabbit-Order: Parallel Community Detection<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-431\" data-id=\"431\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-17.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Rabbit-Order: Parallel Community Detection<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-432\" data-id=\"432\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-18.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Rabbit-Order: Parallel Community Detection<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-433\" data-id=\"433\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-19.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Push Locality vs. Pull Locality<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-434\" data-id=\"434\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-20.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Push Locality vs. Pull Locality<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-435\" data-id=\"435\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-21.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Conclusion<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-436\" data-id=\"436\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-22.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">Thanks<\/figcaption><\/figure><\/li><li class=\"wp-block-jetpack-slideshow_slide swiper-slide\"><figure><img decoding=\"async\" alt=\"\" class=\"wp-block-jetpack-slideshow_image wp-image-437\" data-id=\"437\" src=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/wp-content\/uploads\/sites\/14\/2023\/02\/How-Do-Graph-Relabeling-Algorithms-Improve-Memory-Locality-ISPASS21-23.png\" \/><figcaption class=\"wp-block-jetpack-slideshow_caption gallery-caption\">QUB<\/figcaption><\/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<\/div><\/div>\n<\/div>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div><\/div>\n\n\n\n<p><strong>Code Availability<\/strong><br>The source-code of LaganLighter is available on<a href=\"https:\/\/blogs.qub.ac.uk\/DIPSA\/LaganLighter-Source-Code\/\"> <strong>LaganLighter Repository<\/strong><\/a>.<\/p>\n\n\n\n<p><strong>BibTex<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>@INPROCEEDINGS{10.1109\/ISPASS51385.2021.00023,\n  author={Koohi Esfahani, Mohsen and Kilpatrick, Peter and Vandierendonck, Hans},\n  booktitle={2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)}, \n  title={How Do Graph Relabeling Algorithms Improve Memory Locality?}, \n  year={2021},\n  volume={},\n  number={},\n  pages={84-86},\n  publisher={IEEE Computer Society},\n  doi={10.1109\/ISPASS51385.2021.00023}\n}\n<\/code><\/pre>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.ispass.org\/ispass2021\/\" target=\"_blank\"><strong>ISPASS&#8217;21<\/strong><\/a><br><strong><a href=\"http:\/\/ispass.org\/ispass2021\/program.php\">ISPASS&#8217;21 Final Program<\/a><\/strong><br><a href=\"\/DIPSA\/LaganLighter\"><strong>LaganLighter<\/strong><\/a><\/p>\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>Relabeling (reordering) algorithms aim to improve the poor memory locality of graph processing by changing the order of vertices. This paper analyses the functionality of three state-of-the-art relabeling algorithms: SlashBurn, GOrder, and Rabbit-Order for real-world graphs.<\/p>\n<p>We use a number of techniques to explain how locality is affected by relabeling algorithms and how locality of different datasets (like social networks, web graphs) is enhanced by relabeling algorithms.<\/p>\n<p>This paper also investigates why different push and pull traversal of different datasets show different behaviours by introducing push locality and pull locality.  <\/p>\n","protected":false},"author":1315,"featured_media":1627,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[40],"tags":[34,35,36,37,38,39,26,41,42],"class_list":{"0":"post-1622","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-graph-processing","10":"tag-graph-relabeling","11":"tag-graph-traversal","12":"tag-high-performance-computing","13":"tag-laganlighter","14":"tag-locality","15":"tag-push-and-pull-locality","16":"tag-spmv","17":"czr-hentry"},"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2022\/12\/header-11.jpg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1622","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=1622"}],"version-history":[{"count":2,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1622\/revisions"}],"predecessor-version":[{"id":2623,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/1622\/revisions\/2623"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/1627"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=1622"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=1622"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=1622"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}