Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

2-25-2018

Journal or Book Title

Concurrency and Computation: Practice and Experience

Volume

30

Issue

4

First Page

e4333

DOI

10.1002/cpe.4333

Abstract

The incremental graph connectivity (IGC) problem is to maintain a data structure that can quickly answer whether two given vertices in a graph are connected, while allowing more edges to be added to the graph. IGC is a fundamental problem and can be solved efficiently in the sequential setting using a solution to the classical union‐find problem. However, sequential solutions are not sufficient to handle modern‐day large, rapidly‐changing graphs where edge updates arrive at a very high rate. We present the first shared‐memory parallel data structure for union‐find (equivalently, IGC) that is both provably work‐efficient (ie, performs no more work than the best sequential counterpart) and has polylogarithmic parallel depth. We also present a simpler algorithm with slightly worse theoretical properties, but which is easier to implement and has good practical performance. Our experiments on large graph streams with various degree distributions show that it has good practical performance, capable of processing hundreds of millions of edges per second using a 20‐core machine.

Comments

This is the peer-reviewed version of the following article: Simsiri, Natcha, Kanat Tangwongsan, Srikanta Tirthapura, and Kun‐Lung Wu. "Work‐efficient parallel union‐find." Concurrency and Computation: Practice and Experience 30, no. 4 (2018): e4333, which has been published in final form at doi: 10.1002/cpe.4333. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving. Posted with permission.

Copyright Owner

John Wiley & Sons, Ltd.

Language

en

File Format

application/pdf

Available for download on Monday, February 25, 2019

Published Version

Share

COinS