异构信息网上的可达性查询
随着图数据规模的爆炸式增长,其形式也越来越复杂异构信息网可建模成包含多种类型的顶点和多种类型的边的图例如,文献数据库、在线购物网站等首次研究异构信息网上的可达性查询问题利用不同类型顶点之间的关系,查询两个顶点满足路径模式的可达性,该问题的时间复杂度是多项式的然而在大规模的网络上,每次查询遍历一遍网络的时间开销也是不能容忍的现有的可达性查询问题主要分为两类:k跳可达性查询和带有标签约束的可达性查询但是这两种问题的算法都不能用于解决异构信息网上的可达性查询问题因此,为了实现高效的在线查询,提出一种新的索引结构,通过路径模式的分解,预先计算部分路径模式的可达信息当在线查询到来时,在路径模式的偏序图上,快速找到索引结构中存在的路径子模式,高效地计算查询结果在真实和人工数据集上进行了大量实验,验证了算法的有效性.
异构信息网 信息查询 路径选择 运行效率
尹丹 高宏 邹兆年 李建中
哈尔滨工业大学计算机科学与技术学院 哈尔滨150001
国内会议
北京
中文
1-11
2014-12-01（万方平台首次上网日期，不代表论文的发表时间）