Quanquan Liu Wins the Best Paper Award at the 2022 ACM SPAA Conference

Quanquan Liu, a postdoctoral scholar in the Northwestern CS Theory Group mentored by Northwestern Engineering’s Samir Khuller, won Best Paper Award at the 34th Association for Computing Machinery (ACM) Symposium on Parallelism in Algorithms and Architectures (SPAA 2022), held last month in Philadelphia.

Liu’s winning paper, “Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems,” presents the first provably efficient parallel, batch-dynamic algorithm for approximate 𝑘-core decomposition in dynamic graphs under large batches of edge updates. The k-core decomposition — or the largest subgraph of a network in which each node has at least k neighbors — is an important metric for detecting communities of individuals (nodes) which have close ties with one another.

Large-scale graphs are rapidly evolving with thousands or even millions of updates each second. Thus, Liu explained, it is important to find scalable algorithms that take advantage of parallel architectures.

“Our experimental results demonstrate orders-of-magnitude speedups against state-of-the-art implementations on large real-world graphs, suggesting our algorithms are also practical in real-world systems,” Liu said.

The paper is coauthored by Jessica Shi and Shangdi Yu [Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology (MIT)]; Laxman Dhulipala (University of Maryland, College Park); and Julian Shun (MIT CSAIL).

“Our paper gives algorithms in bounded arboricity graphs, which were studied quite a lot in the sequential setting but not in the batch-dynamic setting prior to our work,” Liu said. “Many real-world graphs have bounded arboricity and we hope our paper encourages more interest in batch-dynamic algorithms for bounded arboricity graphs.”

The team also applied the parallel level data structure to obtain a set of new theoretical results for related graph problems, including low out-degree orientation, maximal matching, clique counting, and vertex coloring.

Liu is pursuing a faculty position in computer science or related fields. Long-term, she aims to continue research in scalable graph algorithms, in both theory and practice, and to explore connections between scalable graph algorithms and other algorithmic considerations like differential privacy.

Liu earned a PhD in computer science from the MIT Theory Group advised by Shun and Erik D. Demaine. Prior to joining Northwestern CS, she completed a postdoctoral fellowship at MIT mentored by Shun and was a student researcher with the Google Discrete Algorithms Group.

Additional Northwestern CS papers at SPAA 2022

National Science Foundation Computing Innovation Fellow Sami Davies presented her work in collaboration with her postdoctoral adviser Khuller, Peter and Adrienne Barris Chair of Computer Science at the McCormick School of Engineering, and visiting scholar Shirley Zhang. The paper, “Balancing Flow Time and Energy Consumption,” presents a batch scheduling model that provides dynamic programs which minimize flow time subject to active time constraints. Zhang presented the paper at the 15th Workshop on Models and Algorithms for Planning and Scheduling in June.

In addition, Andrew Crotty, incoming assistant professor of computer science at Northwestern Engineering, coauthored the paper titled “HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures,” presented at SPAA 2022 by Jiwon Choe (Brown University). Additional coauthors include Tali Moreshet (Boston University), Maurice Herlihy (Brown University), and R. Iris Bahar (Colorado School of Mines).

To process data with traditional hardware, it must first be transferred from memory to the CPU. Near-memory processing (NMP) refers to a new type of hardware that adds compute capabilities to the memory, meaning that data can now be processed directly where it resides without transferring it to the CPU. The research team explored how best to redesign commonly used data structures, which allow applications to quickly find and retrieve data of interest, to leverage the unique characteristics of NMP architectures.

“NMP architectures are particularly exciting because they can make workloads run faster while also significantly reducing energy consumption. However, since they are fundamentally different from traditional architectures, completely new techniques are necessary to take advantage of their unique properties,” Crotty said. “The results show that our techniques achieve more than double the performance of existing approaches. Our work redesigns two widely used data structures from the ground up to fully leverage emerging NMP hardware and lays a strong foundation for future work in this area.”

SPAA 2022 was sponsored by the ACM Special Interest Groups on Algorithms and Computation Theory (SIGACT) and Computer Architecture (SIGARCH) and organized in cooperation with the European Association for Theoretical Computer Science.