基于Swap半外存图算法的降低大量随机访问产生的开销方法

摘要

本发明属于大图数据处理技术领域，公开了一种基于Swap半外存图算法的降低大量随机访问产生的开销方法，内存数据结构由一个3|V|大小的三维数组构成；id作为图中一个点的编号；lineage表示该点的归属信息，表示该点归属于哪一个交换结构；点1和点4的lineage信息都为u；state是一个集合包含了K,N,C,A,P五个状态，用来描述和定义算法。本发明在半外存Greedy算法的基础上，基于Scan和状态转换的操作。对于one‑k‑swap的过程而言，每一个迭代需要进行三轮Scan，在每一轮当中的状态转换会按照状态转换规则来进行转换，算法持续进行迭代，直到本次迭代中不会再有swap的情况发生。