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

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

作者：尹丹,高宏,邹兆年,李建中,

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

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