近年来，大数据处理受到广泛关注。以Web图和在线社交网络为代表的大规模图作为一类应用广泛的大数据，其规模在持续快速增长，给处理系统带来更高要求。在图处理应用中，图中的三角形作为衡量顶点间联系紧密程度的重要结构，是图结构分析的重要基础。相应地，三角形计算，即枚举出图中所有三角形或统计三角形数目，成为一类重要的基础算法，广泛应用于各类场景下，如检测在线垃圾信息发送行为、评估在线内容的质量、理解蛋白质作用网络等。大规模图的三角形计算的挑战，主要来自图中顶点间连接的随机性导致的随机访存占比大和分布式处理时产生的大量网络消息。
　　共享内存环境下的三角形计算可避免网络消息，且可利用内存的更快速度和对随机访问的更好支持，从而使共享内存处理较之中小规模集群上的分布式处理性价比更高、实现更容易、效率更高。但单机有限的内存空间和图的巨大规模之间的矛盾严重制约了共享内存三角形计算的应用范围，从而使得图压缩很有必要，其难点在于既要保证压缩率又要不影响速度，甚至提升速度。针对此问题提出一种轻量压缩方案CIC-PIM(Chunked Index Compression for Parallel In-Memory graph processing)，选用合适的轻量技术压缩非索引数据，利用大规模图中普遍存在的幂律性和稀疏性压缩索引数据。基本思路是将索引分成长度合适的块，从而带来良好的可压缩性，并用对齐到字节的定长编码压缩索引块，从而实现良好的压缩率、完全的随机访问支持、较高的缓存利用率等。相比典型的共享内存图压缩方案Ligra+，CIC-PIM实现了69%的索引压缩率，从而将整图压缩率提升了24%达到52%，同时提高了8%的处理速度。
　　为了对更大规模的图进行内存处理，需要进行分布式内存三角形计算。图中顶点间连接的随机性导致大量网络消息，大幅减少甚至消除网络消息便成为最大挑战。为此提出解决方案LiteTE(Lite Triangle Enumerating)，它主要包含如下技术：(1)面向内存资源的图分割，通过把图均衡地分割成合适的大子图，同时结合现有的消息合并技术，解决了大量网络消息问题；(2)三级负载均衡策略，通过子图、节点、线程三级轻量负载均衡技术，改善负载均衡的同时避免高额开销；(3)高速数据广播算法，通过所有节点间的同步收发数据充分挖掘每个节点的双向网络带宽，大幅提升数据传输速度。实验显示，相比典型的分布式三角形计算方案Surrogate、HavoqGT和PTE，LiteTE大幅减少了网络消息，改善了负载均衡效果，平均将计算速度提升了49倍，同时显著改善了扩展性。
　　当图规模继续增大时，就需要采用分布式外存计算模式。除了和分布式内存计算一样存在大量网络消息问题之外，分布式外存三角形计算还存在如何缩减中间数据和高效利用集群I/O带宽的问题。已有工作因大量网络消息和中间数据、资源利用率低下而导致计算效率很低，为此，本文提出解决方案HOSA(Hold One and Shift Another)，主要包括：(1)一种无重叠的图分割与放置策略，基于图的邻居列表和边列表格式，均衡分割邻居列表并根据邻居列表分割边列表，从而得到不重叠的子图，并把子图均衡的发送到各节点上，大幅减少中间数据的同时有效利用I/O带宽；(2)提出基于数据预传输的计算策略，将计算过程分成相互交错的两类阶段，包括传输阶段和处理阶段，在每个传输阶段将随后处理阶段需要的数据充分利用集群的网络和I/O带宽扩散至各节点，随后的处理阶段所需的数据便可全部在本地找到，从而避免网络消息，提高资源利用率。实验显示，相比典型的分布式三角形计算方案HavoqGT和PTE，HOSA将计算速度分别提升了6.4倍和57倍。相比分布式内存计算方案LiteTE，HOSA达到其计算速度的75%，但能处理的图规模提升了20倍。