German philosopher Friedrich Nietzsche once said, “Invisible threads are the strongest bonds.” One may think “invisible threads” connecting related objects, just like the houses on a delivery driver’s route, or more nebulous entities, like transactions in a financial network or user on a social network.
Computer scientist Julian Shun studies most of these multi-layered but often invisible connections using diagrams wherein objects are represented as points or vertices and the relationships between them are modeled by line segments or edges.
Shun, a brand new associate professor within the Department of Electrical Engineering and Computer Science, is designing graph algorithms that would determine the shortest path between houses on the delivery driver's route or detect fraudulent transactions by malicious actors on a financial network.
But as the quantity of information has increased, such networks have grown to incorporate billions and even trillions of objects and connections. To find efficient solutions, Shun develops high-performance algorithms that use parallel computing to quickly analyze even the biggest graphs. Since parallel programming is notoriously difficult, he also develops user-friendly programming frameworks that make it easier for others to jot down their very own efficient graph algorithms.
“When you seek for something on a search engine or social network, you need to get results in a short time. If you're attempting to discover fraudulent financial transactions at a bank, you need to do it in real time to attenuate damage. Parallel algorithms can speed up work by consuming more computing resources,” explains Shun, who can also be a senior researcher on the Computer Science and Artificial Intelligence Laboratory (CSAIL).
Such algorithms are sometimes utilized in online advice systems. Search for a product on an e-commerce site and likelihood is you'll quickly see a listing of related items that you could possibly also add to your shopping cart. This list is created using graphing algorithms that leverage parallelism to quickly find related items across an unlimited network of users and available products.
Campus Connections
Shun's only experience with computers as a youngster was a highschool course in website constructing. He was more occupied with math and science than engineering and desired to major in one in every of these subjects when he enrolled as an undergraduate on the University of California, Berkeley.
But in his first yr, a friend really helpful he take an introductory computer science course. Although 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 remembers.
The first computer science course was self-study, so Shun taught himself many of the material. He liked the logical facets of algorithm development and the short feedback loop in computer science problems. Shun could enter his solutions into the pc and immediately see whether he was right or improper. And the errors within the improper solutions would lead him to the appropriate answer.
“I've all the time thought that constructing things is fun, and programming is about constructing solutions that do something useful. That appealed to me,” he adds.
After graduating, Shun spent a while in industry but soon realized he desired to pursue an educational profession. He knew that at a university he would have the liberty to work on problems that interested him.
Getting began with graphics
He enrolled as a graduate student at Carnegie Mellon University, where his research focused on applied algorithms and parallel computing.
As a student, Shun had taken theoretical algorithm courses and practical programming courses, however the two worlds didn't fit together. He desired to conduct research that combined theory and application. Parallel algorithms were an ideal fit.
“With parallel computing, you’ve gotten to fret 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, they won’t be as useful,” he says.
At Carnegie Mellon, he learned about graph datasets wherein objects in a network are modeled as vertices connected by edges. He was interested in the numerous applications of this sort of data set and the challenge of developing efficient algorithms to process them.
After completing a postdoctoral fellowship at Berkeley, Shun searched for a college position and decided to affix MIT. He had collaborated with several MIT faculty members on parallel computing research and was excited to affix an institute with such broad expertise.
In one in every of his first projects after joining MIT, Shun developed a graph processing programming framework called GraphIt with Saman Amarasinghe, professor within the Department of Electrical Engineering and Computer Science and CSAIL member, an authority in programming languages ​​and compilers. The easy-to-use framework, which generates efficient code from high-level specifications, was about five times faster than the following best approach.
“It was a really fruitful collaboration. If I had worked alone, I might not have been in a position to develop such a strong solution,” he says.
Shun also expanded his research focus to incorporate clustering algorithms, which aim to group related data points. He and his students develop parallel algorithms and frameworks to quickly solve complex clustering problems that could be used for applications reminiscent of anomaly detection and community detection.
Dynamic problems
Lately, he and his collaborators have been specializing in dynamic problems, where data in a graph network changes over time.
When a knowledge set comprises billions or trillions of information points, running an algorithm from scratch to make a small change could be extremely costly from a computational perspective. He and his students design parallel algorithms that process many updates concurrently, improving efficiency while maintaining accuracy.
But these dynamic issues also represent one in every of the most important challenges that Shun and his team must work to beat. Since there aren’t many dynamic data sets available for testing algorithms, the team often has to generate synthetic data that will not be realistic and will affect the performance of their algorithms in the true world.
Ultimately, his goal is to develop dynamic graph algorithms that work efficiently in practice while at the identical time withstanding theoretical guarantees. This ensures they’re applicable in a big selection of environments, he says.
Shun assumes that dynamic parallel algorithms will change into a good greater research focus in the long run. As data sets change into larger, more complex, and more rapidly changing, researchers must develop more efficient algorithms to maintain up.
He also expects that advances in computing technology will bring recent challenges as researchers must design recent algorithms to reap the benefits of the properties of novel hardware.
“That’s the fantastic thing about research – I can try to unravel problems that other people have never solved and contribute something useful to society,” he says.
