Data Structures for Efficient Parallel Graph Processing

Дата публикации: 20-07-2026 00:00:00

We present the Toggle Tree, a parallel data structure for frontier-based graph algorithms. A Toggle Tree is used to represent a subset of vertices using hierarchical bit vectors, enabling efficient parallel updates, traversal, and set-wise reductions without global packing. It provides an IndexSet interface that unifies a wide range of parallel graph algorithms un- der a common abstraction of frontiers and active sets, and an IndexMap interface that also incorporates priority-queue semantics. Specifically, the Toggle Tree aims to combine the advantages of traditional sparse and dense frontier representations, offering both provable theoretical guarantees and high efficiency in practice.Using Toggle Trees, we implement five fundamental graph algorithms, including breadth-first search (BFS), k-core, degree-based graph coloring, single-source shortest paths using Bellman-Ford, and weighted-BFS (wBFS). Across a diverse set of large real-world graphs and the five graph problems, our...

Схожие новости

#	Наименование новости	Тональность	Информативность	Дата публикации
1	Linear complexity	0	7.34	18-08-2026
2	Two-way Node Popularity Model for Directed and Bipartite Networks	0	9.3	17-08-2026
3	Limiting Over-Smoothing and Over-Squashing of Graph Message Passing by Deep Scattering Transforms	0	10.87	17-08-2026
4	Hybrid Phased Arrays for Mass Market Satellite User Terminals: Balancing Performance, Cost and Interference Resilience	0	10	12-05-2026
5	Backend-for-Frontend: The most secure architecture for browser-based apps	0	24.06	22-04-2026
6	Writing a TOON Module for Perl	0	7.96	29-03-2026
7	RAG vs. Agentic RAG: Architecture, Tradeoffs, and How to Choose	0	7.77	29-07-2026
8	The Role of Precision Timing in Enabling Higher Bandwidth Per Rack Without Compromising Signal Integrity or Efficiency	0	10	13-04-2026
9	A Weak Equivalence from the Subdivision of the Orbit Category to the Link Orbit Category for Finite Abelian Groups	0	2.68	20-07-2026
10	When “Highly Available” Isn’t Available Enough: Kubernetes at the Industrial Edge	0	7	26-02-2026

Классификация: Пресс-релизы. Схожих патентов: 0. Схожих новостей: 10. Тональность: 0. Информативность: 7.17. Источник: escholarship.org.