Edward Z. Fan

Edward Z. Fan
MIT EECS Undergraduate Research and Innovation Scholar
Advisor: Julian Shun
Department: EECS
Areas of Research: Theory of Computer Systems
Years: 2018-2019
Research Project Title:

Concurrent Union-Find

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."