The German philosopher Fredrich Nietzsche once said that “invisible threads are the strongest ties.” One could consider “invisible threads” as tying together related objects, just like the homes on a delivery driver’s route, or more nebulous entities, corresponding to transactions in a financial network or users in a social network.
Computer scientist Julian Shun studies all these multifaceted but often invisible connections using graphs, where objects are represented as points, or vertices, and relationships between them are modeled by line segments, or edges.
Shun, a newly tenured associate professor within the Department of Electrical Engineering and Computer Science, designs graph algorithms that might be used to seek out the shortest path between homes on the delivery driver’s route or detect fraudulent transactions made by malicious actors in a financial network.
But with the increasing volume of information, such networks have grown to incorporate billions and even trillions of objects and connections. To search out efficient solutions, Shun builds high-performance algorithms that leverage parallel computing to rapidly analyze even probably the most enormous graphs. As parallel programming is notoriously difficult, he also develops user-friendly programming frameworks that make it easier for others to jot down efficient graph algorithms of their very own.
“In the event you are trying to find something in a search engine or social network, you desire to get your results in a short time. In the event you are attempting to discover fraudulent financial transactions at a bank, you desire to achieve this in real-time to reduce damages. Parallel algorithms can speed things up by utilizing more computing resources,” explains Shun, who can be a principal investigator within the Computer Science and Artificial Intelligence Laboratory (CSAIL).
Such algorithms are steadily utilized in online advice systems. Seek for a product on an e-commerce website and odds are you’ll quickly see an inventory of related items you could possibly also add to your cart. That list is generated with the assistance of graph algorithms that leverage parallelism to rapidly find related items across an enormous network of users and available products.
Campus connections
As an adolescent, Shun’s only experience with computers was a highschool class on constructing web sites. More taken with math and the natural sciences than technology, he intended to major in considered one of those subjects when he enrolled as an undergraduate on the University of California at Berkeley.
But during his first 12 months, a friend beneficial he take an introduction to computer science class. While he wasn’t sure what to anticipate, he decided to enroll.
“I fell in love with programming and designing algorithms. I switched to computer science and never looked back,” he recalls.
That initial computer science course was self-paced, so Shun taught himself many of the material. He enjoyed the logical elements of developing algorithms and the short feedback loop of computer science problems. Shun could input his solutions into the pc and immediately see whether he was right or mistaken. And the errors within the mistaken solutions would guide him toward the proper answer.
“I’ve all the time thought that it was fun to construct things, and in programming, you might be constructing solutions that do something useful. That appealed to me,” he adds.
After graduation, Shun spent a while in industry but soon realized he desired to pursue an educational profession. At a university, he knew he would have the liberty to review problems that interested him.
Stepping into graphs
He enrolled as a graduate student at Carnegie Mellon University, where he focused his research on applied algorithms and parallel computing.
As an undergraduate, Shun had taken theoretical algorithms classes and practical programming courses, however the two worlds didn’t connect. He desired to conduct research that combined theory and application. Parallel algorithms were the proper fit.
“In parallel computing, you’ve got to care about practical applications. The goal of parallel computing is to hurry things up in real life, so in case your algorithms aren’t fast in practice, then they aren’t that useful,” he says.
At Carnegie Mellon, he was introduced to graph datasets, where objects in a network are modeled as vertices connected by edges. He felt drawn to the various applications of all these datasets, and the difficult problem of developing efficient algorithms to handle them.
After completing a postdoctoral fellowship at Berkeley, Shun sought a school position and decided to hitch MIT. He had been collaborating with several MIT faculty members on parallel computing research, and was excited to hitch an institute with such a breadth of experience.
In considered one of his first projects after joining MIT, Shun joined forces with Department of Electrical Engineering and Computer Science professor and fellow CSAIL member Saman Amarasinghe, an authority on programming languages and compilers, to develop a programming framework for graph processing referred to as GraphIt. The simple-to-use framework, which generates efficient code from high-level specifications, performed about five times faster than the following best approach.
“That was a really fruitful collaboration. I couldn’t have created an answer that powerful if I had worked by myself,” he says.
Shun also expanded his research focus to incorporate clustering algorithms, which seek to group related datapoints together. He and his students construct parallel algorithms and frameworks for quickly solving complex clustering problems, which could be used for applications like anomaly detection and community detection.
Dynamic problems
Recently, he and his collaborators have been specializing in dynamic problems where data in a graph network change over time.
When a dataset has billions or trillions of information points, running an algorithm from scratch to make one small change might be extremely expensive from a computational viewpoint. He and his students design parallel algorithms that process many updates at the identical time, improving efficiency while preserving accuracy.
But these dynamic problems also pose considered one of the most important challenges Shun and his team must work to beat. Because there aren’t many dynamic datasets available for testing algorithms, the team often must generate synthetic data which will not be realistic and will hamper the performance of their algorithms in the true world.
Ultimately, his goal is to develop dynamic graph algorithms that perform efficiently in practice while also holding as much as theoretical guarantees. That ensures they shall be applicable across a broad range of settings, he says.
Shun expects dynamic parallel algorithms to have an excellent greater research focus in the long run. As datasets proceed to develop into larger, more complex, and more rapidly changing, researchers might want to construct more efficient algorithms to maintain up.
He also expects recent challenges to return from advancements in computing technology, since researchers might want to design recent algorithms to leverage the properties of novel hardware.
“That’s the great thing about research — I get to try to solve problems other people haven’t solved before and contribute something useful to society,” he says.
