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

摘要：

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

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

所属期刊栏目：52

分类号：TP392(计算技术、计算机技术)

资助基金：国家自然科学基金项目61379050,91224008;国家“八六三”高技术研究发展计划基金项目2013AA013204;高等学校博士学科点专项科研基金项目20130004130001

在线出版日期：2015-04-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：116-129