Open Collections

Sallinen, Scott

University of British Columbia

The rapid increase in connected data from various sources such as the World Wide Web, social networks, and financial transactions has led to the widespread use of graph-based representations for data analysis of these networks. However, traditional high-performance computing (HPC) solutions designed for static graphs are inefficient and impractical for dynamic graphs that evolve over time. This approach leads to high overheads, loss of information between snapshots, and potential correctness issues. The demand for fast, real-time analytics on continuously evolving real-world systems at a massive scale has become critical for applications such as online recommendations, financial fraud detection, and counter-terrorism. For example, social media networks like Facebook handle potentially millions of interactions per second, and payment networks like Visa process thousands of transactions per second. To address these challenges, my dissertation focuses on the opportunities and challenges of analyzing dynamic graphs in real-time, offering an infrastructure-algorithm co-design for dynamic graph analytics at scale. To this end, I develop and present a pattern for dynamic graph algorithms, and a supporting software infrastructure architecture, that together form a cohesive real-time graph analysis model. My algorithm pattern is designed to be amenable to distributed systems with concepts such as message passing, asynchronicity, and termination, while considering the timeliness requirements for real-time analysis. The infrastructure architecture considers real-world properties of dynamic data generation and hardware constraints, aiming for versatility, performance, and scalability. It supports dynamic graph topology evolution and provides interfaces for expressing algorithms for dynamic graph analysis and collecting results during runtime. I demonstrate that many common static graph algorithms can be re-designed for dynamic processing and real-time analysis, and can be built and scaled efficiently. My dynamic graph model offers advantages over static designs, such as low-cost updates to the graph and the ability to observe algorithm results before or after topology modifications. The implementation of my model shows near-linear scalability in performance, and supports real-time analysis at potentially orders of magnitude higher evolution rates compared to alternative designs; providing a generic, scalable, and performant solution for dynamic graph analysis, addressing the challenges of analyzing large-scale, continuously evolving network data in real-time.

Text

2024-01-08

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/87143

Electrical and Computer Engineering

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/