异构信息网上的可达性查询

摘要：

随着图数据规模的爆炸式增长,其形式也越来越复杂.异构信息网可建模成包含多种类型的顶点和多种类型的边的图.例如,文献数据库、在线购物网站等.首次研究异构信息网上的可达性查询问题.利用不同类型顶点之间的关系,查询2个顶点满足路径模式的可达性,该问题的时间复杂度是多项式的.然而在大规模的网络上,每次查询遍历一遍网络的时间开销也是不能容忍的.现有的可达性查询问题主要分为2类:k跳可达性查询和带有标签约束的可达性查询.但是这2种问题的算法都不能用于解决异构信息网上的可达性查询问题.因此,为了实现高效的在线查询,提出一种新的索引结构,通过路径模式的分解,预先计算部分路径模式的可达信息.当在线查询到来时,在路径模式的偏序图上,快速找到索引结构中存在的路径子模式,高效地计算查询结果.在真实和人工数据集上进行了大量实验,验证了算法的有效性.

关键词：异构信息网、查询处理、可达性、路径模式、索引

所属期刊栏目：53

分类号：TP311.1(计算技术、计算机技术)

资助基金：国家“九七三”重点基础研究发展计划基金项目2012CB316200;国家自然科学基金重点项目61033015;国家自然科学基金重大项目61190115,60933001;国家自然科学基金面上项目61173023This work was supported by the National Basic Research Program of China 973 Program2012CB316200;the Key Program of the National Natural Science Foundation of China61033015;the Major Program of the National Natural Science Foundation of China61190115,60933001;the General Program of the National Natural Science Foundation of China61173023

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

页数：共13页

页码：479-491