论文部分内容阅读
图在生活中扮演着至关重要的作用。在大数据时代，越来越多的应用将信息抽象成图数据，并使用图算法对图数据进行处理，例如社交网络图，路图，网络路由图等。由于现实信息随着时间逐渐变化，原始的静态图数据逐渐演变成了多版本图数据，图的规模也逐渐变大。如何对多个版本的大图中的大量数据进行存储和随机版本访问，成为了图处理中的新的问题。对多版本图数据的处理，现有的方法有的会导致海量的存储空间开销和高度的存储冗余。有的则会在版本切换中花费大量的时间。
经过分析发现，现有的对多版本图数据的处理有如下特点：1)在图的演变过程中，对内存影响较大的点是度较高的点。这些点不仅占据整个图的大部分边，同时也有明显更高的变化倾向。而度较低的点则更加倾向于不发生变化。2)在对所有的版本的访问频率分布上，较新版本的被访问频率明显高于其他版本。对这些版本的访问进行优化可能对整体的平均访问速度有较大提升。
提出的Pensieve系统是一个倾斜感知的多版本图处理系统。Pensieve主要从两个方面提升了处理效率。首先，针对图结构倾斜问题，Pensieve使用了一种点区分的图存储策略，对度低的点使用复制方法保留其易访问性，同时对度高的点使用基于重演的方法降低内存开销。在多版本图处理中，这种策略在存储开销和版本切换时间方面做出了较好的权衡，使得整个系统可以在较低的存储开销上进行较快的版本切换。其次，得益于图处理中版本访问频率的倾斜，Pensieve设计并实现了一个最终根回溯的方案，使得访问频率较高的版本在更为容易获取到的地方，显著提升了新近版本的访问效率。对于最终根回溯带来的大量删除边的问题，Pensieve通过索引删除方法，大大降低了在数组中进行删除的时间开销，加速了版本切换的速度。Pensieve同时还有多个细节优化点。在真实数据集上的实验结果表明，Pensieve在多个数据集上的表现明显优于其他方案。在综合效率上相比当前最好的方案提升了40%-95%不等。
经过分析发现，现有的对多版本图数据的处理有如下特点：1)在图的演变过程中，对内存影响较大的点是度较高的点。这些点不仅占据整个图的大部分边，同时也有明显更高的变化倾向。而度较低的点则更加倾向于不发生变化。2)在对所有的版本的访问频率分布上，较新版本的被访问频率明显高于其他版本。对这些版本的访问进行优化可能对整体的平均访问速度有较大提升。
提出的Pensieve系统是一个倾斜感知的多版本图处理系统。Pensieve主要从两个方面提升了处理效率。首先，针对图结构倾斜问题，Pensieve使用了一种点区分的图存储策略，对度低的点使用复制方法保留其易访问性，同时对度高的点使用基于重演的方法降低内存开销。在多版本图处理中，这种策略在存储开销和版本切换时间方面做出了较好的权衡，使得整个系统可以在较低的存储开销上进行较快的版本切换。其次，得益于图处理中版本访问频率的倾斜，Pensieve设计并实现了一个最终根回溯的方案，使得访问频率较高的版本在更为容易获取到的地方，显著提升了新近版本的访问效率。对于最终根回溯带来的大量删除边的问题，Pensieve通过索引删除方法，大大降低了在数组中进行删除的时间开销，加速了版本切换的速度。Pensieve同时还有多个细节优化点。在真实数据集上的实验结果表明，Pensieve在多个数据集上的表现明显优于其他方案。在综合效率上相比当前最好的方案提升了40%-95%不等。