马洪宾,陈贵海

(上海交通大学计算机科学与工程系,上海200240)

图引擎底层存储的设计与实现

马洪宾,陈贵海

(上海交通大学计算机科学与工程系,上海200240)

随着社交网络和语义Web等数据应用的兴起,催生了许多图数据处理产品,包括Neo4j,HyperGraphDB等,然而这些产品在设计时并未充分考虑图应用对数据可用性和可扩展性的更高要求。为此,提出一种基于分布式内存云的图引擎底层建模和存储解决方案。在内存云上搭建分布式键值引擎,进而在键值存储的基础上对图的数据进行建模和读写。在大规模数据集上的实验结果表明,该方案具有较好的图随机访问性能,并能够高效地支持海量规模的图数据应用。

图处理;云计算;分布式;数据建模;存储;数据结构

1 概述

图是最常见的数据结构之一,与线性表和树相比,它的结构更加复杂,对数据的表现能力也更丰富。传统的图应用包括道路分析［1］、论文引用分析［2］、网页链接分析［3］等。 随着社交网络［4-5］、语义网络［6］等研究领域的兴起,由于图在表示实体间关系方面的显著优势,因此越来越多的研究尝试使用图来存储和挖掘数据。

学术界和工业界已有大量工作致力于图的应用和理论研究。截止目前,已有很多图数据库产品可供选择。但是随着数据规模的日益增长,图的规模也随之呈现爆发式增长的趋势。如何有效地存储和使用海量规模的图数据集,成为图数据库领域内的一大难题。

本文结合图数据应用对……