【斯坦福博士论文】用于系统设计的图算法，130页pdf

图是数据和系统表示的强大工具。许多类型的复杂和高度结构化的数据都可以用图表示，比如社交网络、计算机网络和分子。图还可以用来表示计算机系统，例如分布式存储网络和对等通信网络。在本论文中，我们讨论了处理大规模图数据和使用图来设计更好的系统的方法。

我们首先讨论两种处理大规模图数据的方法。虽然它们非常强大，但图数据集对其处理和存储提出了独特的挑战。图神经网络(GNNs)是将深度学习应用于图结构数据的一种有效方法。但是，由于图的互连和高度结构化的特性，训练GNN的计算可能非常昂贵。研究了一种提高GNN训练效率的分层聚合方法。另一种理解图数据集的方法是检查小的、重复的模式的频率。我们提出了时间活动状态块模型(Temporal Activity State Block Model)，这是一种用于计算时间图中预期母题频率的分析模型，它增加了边在大时间跨度内到达的复杂性。

接下来我们将介绍两种应用图来设计更好系统的方法。在分布式存储系统中，在服务器故障的情况下，通常需要使用冗余存储数据，而在何处以及以何种频率创建这种冗余的设计可以表示为一个图问题。部分重复(FR)代码是一种用于实现这一目的的方法，旨在最大化存储容量，同时确保故障节点可以通过从幸存节点发送替换数据来替换。我们提出了负载平衡的分数重复码，这是FR码的加强，有额外的保证，如何迅速地更换失败的节点。接下来我们考虑在对等网络中发送消息的问题。这个问题可以用一个图来表示哪个对等点拥有另一个对等点想要的数据。索引编码是一种设计从中央服务器到一组接收器的客户端通信的方法。我们将这种方法应用于点对点模型，并引入和研究了嵌入索引编码。

https://searchworks.stanford.edu/view/14230534