随机游走是图数据分析中的一个重要工具。与传统的一阶随机游走不同，二阶随机游走在选择下一跳时考虑了前一跳的游走信息，这有利于建模现实世界中的高阶结构。为了满足随机游走的可扩展性，研究人员已经开发了许多基于单机的外存图处理系统。然而，现有的外存图处理系统主要针对一阶随机游走进行设计，在支持二阶随机游走时性能不佳。

信息存储与光显示功能实验室博士生吴雨桐，在施展副教授指导下，提出了一个针对二阶随机游走的I/O优化的外存图处理系统，称为SOWalker。该工作首先提出了一个游走矩阵，以避免加载不可更新的游走并消除无用的游走I/O。其次，开发了一个收益感知的I/O模型，加载累积可更新游走数量最大的多个块，以提高I/O利用率。最后，采用了面向块集的游走更新方案，允许游走在被加载的块集中尽可能多地移动，从而提高了游走更新率。与两个最先进的外存随机游走系统相比，SOWalker显著提高了二阶随机游走的执行效率。

该研究成果被USENIX ATC 2023录用。ATC是系统结构领域最重要的国际会议之一，也是中国计算机学会（CCF）推荐的A类会议。本届会议共收到353篇投稿，共录用65篇论文，录用率约为18.41%。该研究工作得到了国家自然科学基金（No. U22A2027，No. 61832020，No. 61821003及No. 82090044）等项目的资助。

图1：SOWalker整体架构