Workshops Archive

IA^3 - Invited Talk 1 - Maintaining connected components for unending graph streams

Workshop: IA^3 2025 — 15th Workshop on Irregular Applications: Architectures and Algorithms

Authors: Cynthia Phillips (Sandia National Laboratories)

Abstract: Motivated by the properties of (unending) real-world cybersecurity streams, we summarize/sketch an algorithm to maintain a streaming graph and its connected components at single-edge granularity: every edge insertion could be followed by a query related to connectivity. To the best of our knowledge, this is the first streaming graph system to update at that granularity. In cybersecurity graph applications, the input stream typically consists of edge insertions; individual deletions are not explicit. Analysts will maintain as much history as possible and will trigger bulk deletions when necessary. During a bulk deletion (called "aging"), and the associated data-structure repairs, queries are disabled, but the system properly ingests any new edges that arrive. We briefly describe the (distributed parallel) algorithms. We present a (proved) relationship among four quantities for indefinite operation: the proportion of query downtime allowed, the proportion of edges that survive an aging event, the proportion of duplicated edges, and the bandwidth expansion factor. The latter is how much faster processors must communicate with each other than the stream arrival rate. We will also present some experimental results on Intel Sky Lake processors. This algorithm might be of increased interest now with the arrival of systems like Cerebras with extremely fast on-wafer networking.

Back to IA^3 2025 — 15th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing Back to Full Workshop Archive Listing