BiRch:一种处理k步可达性查询的双向搜索算法

作     者：周军锋 陈伟 费春苹 陈子阳 ZHOU Jun-feng;CHEN Wei;FEI Chun-ping;CHEN Zi-yang

作者机构：燕山大学信息科学与工程学院河北秦皇岛066004 河北省计算机虚拟技术与系统集成重点实验室河北秦皇岛066004 

出 版 物：《通信学报》 (Journal on Communications)

年 卷 期：2015年第36卷第8期

页      面：50-60页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(61040023 61272124 61303040 61472339) 河北省教育厅研究计划基金资助项目(Y2012014)~~ 

主　　题：k步可达性查询 双向搜索 广度层数 拓扑层数 

摘      要：针对现有方法低效或索引规模庞大的问题,提出一种双向搜索算法Bi Rch。当判断顶点u是否满足k步可达顶点v时,首先比较u的出度和v的入度,优先处理度小的顶点。其优点体现在使用较小的索引,同时避免由于u的出度过大所带来的效率下降问题;提出基于双向广度层数和双向拓扑层数的剪枝策略来辅助过滤,减少需要访问的顶点数量。基于19个真实数据集进行测试,实验结果从索引构建时间、索引大小、查询响应时间、处理顶点数量以及扩展性方面验证了所提方法相对于现有方法的高效性。