This submission won the first prize in the ‘Faculty of Engineering and Physical Sciences’ category at the ‘Research Culture Poster Competition’ organised by the Graduate School, Queen’s University Belfast in 2021. Two seemingly unrelated fields – biomedical research and road planning – have found common ground through subgraph isomorphism search. […]
Graph Algorithms
57 posts
IEEE CLUSTER 20217-10 SeptemberAcceptance rate: 29.4% DOI: 10.1109/Cluster48925.2021.00042IEEE XplorePDF Version (Authors’ 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 […]
50th International Conference on Parallel Processing (ICPP’21)August 9-12, 2021Acceptance Rate: 26.4% DOI:10.1145/3472456.3472462ACM Digital LibraryPDF Version (Authors’ Copy) This paper investigates the implications made by the structure of real-world graphs with power-law degree distribution on the locality of SpMV graph analytics, and by considering the efficacy of locality optimizing graph reordering […]
In this post, I’ll be introducing the core aspects of my research, discussing the significance of subgraph isomorphism search in graphs, and outlining the objectives and milestones that lay ahead for me in my PhD journey. As you may know, graphs are a fundamental structure in computer science, finding applications […]
Scheduling or distributing the computational workload over multiple threads is a critical and repeatedly performed activity in graph processing workloads. In a recent paper “Reducing the burden of parallel loop schedulers for many‐core processors” published in Concurrency & Computation: Practice & Experience, we investigated the overhead introduced by scheduling. This […]
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. 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. This paper also investigates why different push and pull traversal of different datasets show different behaviours by introducing push locality and pull locality.
https://doi.org/10.1145/3392717.3392753 Vectorization seeks to accelerate computation through data-level parallelism. Vectorization has been applied to graph processing, where the graph is traversed either in a push style or a pull style. As it is not well understood which style will perform better, there is a need for both vectorized push and […]
https://doi.org/10.1145/3293883.3295703 This work proposes Vertex- and Edge-Balanced Ordering (VEBO): balance the number of edges and the number of unique destinations of those edges. VEBO balances edges and vertices for graphs with a power-law degree distribution, and ensures an equal degree distribution between partitions. Experimental evaluation on three shared-memory graph processing […]
https://manycore.org.uk/summerschool.html The Manycore Summer School gives researchers an opportunity to learn theory and practice in a range of emerging manycore technologies, from seven world-leading academic and industrial researchers. Participants engaged with cutting-edge material in lectures, hands-on labs, and interactive poster sessions. The Manycore Summer School was held from Monday 16th to Friday 20th […]