中文摘要：

针对现有方法低效或索引规模庞大的问题,提出一种双向搜索算法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.