大规模图数据可达性索引技术：现状与展望

来源：计算机研究与发展杂志2015年第1期北京时间：

作者：富丽贞,孟小峰,

摘要：随着社交网络、生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时，利用深度优先遍历(depth-firstsearch,DFS)或可达性传递闭包可以很容易处理可达性查询.但是，随着图的规模越变越大，由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大，这2种方法不再适用.因此，许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域，如软件工程、编程语言、分布式计算、社交网络分析、生物网络分析、XML和RDF数据库、路由规划等领域.此外，可达性索引还可用于加速其他图算法，如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着，依据支持的数据规模、数据类型以及查询类别，将现有可达性索引工作进行了分类，并对代表性工作进行分类比较；最后，讨论了现有的大规模图数据可达性索引方法存在的问题，并指出了未来的研究方向.

关键词：可达性, 索引, 查询处理, 编码, 图数据,