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

Bi Rch: a bidirectional search algorithm for k-step reachability queries

作　　者：周军锋[1,2] 陈伟[1] 费春苹 陈子阳[1,2] 

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

出　　处：《通信学报》2015年第8期50-60,共11页Journal on Communications

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

摘　　要：针对现有方法低效或索引规模庞大的问题,提出一种双向搜索算法Bi Rch。当判断顶点u是否满足k步可达顶点v时,首先比较u的出度和v的入度,优先处理度小的顶点。其优点体现在使用较小的索引,同时避免由于u的出度过大所带来的效率下降问题;提出基于双向广度层数和双向拓扑层数的剪枝策略来辅助过滤,减少需要访问的顶点数量。基于19个真实数据集进行测试,实验结果从索引构建时间、索引大小、查询响应时间、处理顶点数量以及扩展性方面验证了所提方法相对于现有方法的高效性。A new bidirectional processing algorithm, namely BiRch was proposed. When checking whether a vertex u can reach v within k steps, BiRch firstly compared the out-degree of u and the in-degree of v, and processed the one with smaller degree, such that to avoid large indexes and the inefficiency due to large degree. Two pruning strategies were proposed based on bidirectional breadth-first levels and bidirectional topological levels, such that to reduce the number of visited vertexes. Experimental results on 19 real datasets verify the efficiency of the proposed method in terms of differ- ent metrics, including indexing time, index size, query processing time, the number of visited vertexes, and scalability.

关 键 词：k步可达性查询 双向搜索 广度层数 拓扑层数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]