Research Project Title:
abstract:A disjoint set data structure (often referred to as union-find) maintains a collection of sets of elements that supports two operations: Union(x, y), which joins the sets that contain x and y, and Find(x), which returns the representative of the set that contains x. Such a data structure has many applications, most notably in efficiently computing connected components and minimum spanning tree/forest (via Kruskal's algorithm). Simple theoretically optimal sequential algorithms exist, and various parallel algorithms have been proposed for conducting multiple Union or Find operations in parallel. I intend to conduct a survey of existing parallel algorithms as well as investigate and implement new approaches to concurrent union-find.
"I'm participating in SuperUROP to apply my performance engineering and systems background to an interesting algorithmic problem. Over the past few years, I've done a lot of similar things in industry, and I'd like to see what I could do with a more constrained problem in a research setting."