The characteristics of today’s real-world networks make even the most basic graph processing tasks (such as computing connected components or shortest paths) challenging.
These networks are often very large and their size can easily exceed the capacity of the main memory of a single commodity machine. Even if a network can fit in a computer’s main memory, it might happen that using well-established optimal algorithms (such as breadth-first search) does not guarantee the computation is carried out fast enough. Whereas the consumer processors’ clock speeds have not been increasing lately, a typical processor’s core count is growing steadily. This motivates looking for efficient parallel algorithms in either the classical shared memory models (PRAM) or more recent massively parallel computation models (such as MapReduce) with input data distributed among multiple machines.
Another challenge that we face is that the networks evolve in time. In a typical scenario, a network can undergo small updates very frequently. The updates are so small that it appears unreasonable to recompute the required information from scratch after each update. This motivation has given rise to a very rich area of dynamic graph algorithms that seeks efficient data structures maintaining properties of dynamic graphs. Most of the work in this area so far has been theoretical. Practical evaluation of dynamic graph algorithms is still in its infancy.
The goal of our team’s research is to design and evaluate new parallel and dynamic algorithms for fundamental graph processing problems. First, we conduct theoretical investigation of what parallel work-depth tradeoffs can be achieved and to what extent these solutions can be robust in dynamic environments. Second, we engineer implementations and perform experimental evaluation of dynamic and parallel graph algorithms for problems of practitioners’ interest.
The team’s research is partially aligned with the goals of the NCN grant 2022/47/D/ST6/02184 “Parallel and exact algorithms for path problems in directed graphs” hosted by IDEAS NCBR.