UC Riverside

Developing scalable and efficient graph systems to support low-latency streaming analysis and high-throughput concurrent query evaluation poses significant challenges. This thesis proposes solutions to address these challenges.

Existing streaming graph systems require prior knowledge of queries; otherwise, they fall back to expensive full query evaluations. The proposed Tripoline system overcomes this by applying principles similar to triangle inequalities in Euclidean geometry, generalizing them for various vertex-specific graph problems. This allows the reuse of existing query results to accelerate new queries. Tripoline achieves a speedup of up to $41.5\times$ compared to traditional streaming graph engines.

Another limitation of streaming graph analysis is that when changes to the graphs become large, the incremental graph computation starts running slower than the full query evaluation. Moreover, present incremental graph algorithms cannot handle edge weight updates elegantly, resorting to a sub-optimal two-phase process. The proposed IncBoost addresses these scalability issues with algorithmic enhancements and system-level optimizations. It employs a novel bottom-up dependency tracing technique to identify vertices affected by edge updates without accessing the graph data. It introduces a direct method for handling edge weight updates. IncBoost scales to handle large update batches with sizes of 30\% to 50\% of the graph and achieves up to a $4.9\times$ speedup over RisGraph.

To enhance the efficiency of a query processing system, concurrent query processing is used for higher throughput. However, efficiency is often hampered by misaligned graph traversals, causing unfavorable last-level cache misses. A runtime system called Glign is developed to address this issue by automatically aligning graph traversals for concurrent queries. Glign features novel optimizations at three levels: (1) the intra-iteration alignment effectively reduces memory footprint for graph traversals; (2) the inter-iteration alignment enlarges the overlapping of vertices for better-shared graph access; (3) a query batch formation strategy predicts query subsets with better affinity for batching. Glign outperforms the state-of-the-art concurrent graph processing systems, achieving speedups of up to $4.7\times$.

To improve the system throughput of graph-based approximate nearest neighbor search (ANNS), this dissertation explores the design of graph construction and search phases, particularly with temporal information. The proposed graph construction algorithm considers the correlation between input queries and the final answers in the time dimension. A fully parameterized best-first search algorithm is also designed for flexible performance tuning. These techniques improve query throughput by up to $1.9\times$ compared to the state-of-the-art {DiskANN} while maintaining recall. Additionally, the constructed graph size can be reduced by up to 30\% without compromising query quality.