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

周军锋; 陈伟; 费春苹; 陈子阳

doi:10.11959/j.issn.1000-436x.2015230

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- BiRch：一种处理k步可达性查询的双向搜索算法
- BiRch:a bidirectional search algorithm for k-step reachability queries
- 通信学报 2015年36卷第8期页码：50-60
- 作者机构：
  
  1. 燕山大学信息科学与工程学院，河北秦皇岛 066004
  2. 河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛 066004
- 作者简介：
  
  [ "周军锋（1977-），男，陕西西安人，博士，燕山大学教授，主要研究方向为XML数据库、字符串相似匹配等。" ]
  [ "陈伟（1980-），女，河北秦皇岛人，燕山大学博士生，主要研究方向为数据库理论。" ]
  [ "费春苹（1990-），女，河北秦皇岛人，燕山大学硕士生，主要研究方向为图数据管理。" ]
  [ "陈子阳（1973-），男，黑龙江五常人，博士、燕山大学教授、博士生导师，主要研究方向为数据库理论与系统等。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61040023);国家自然科学基金资助项目(61272124);国家自然科学基金资助项目(61303040);：国家自然科学基金资助项目(61472339);河北省教育厅研究计划基金资助项目(Y2012014)
- DOI：10.11959/j.issn.1000-436x.2015230
  中图分类号： TP391
- 网络出版日期：2015-08，
  
  纸质出版日期：2015-08-25
- 稿件说明：
移动端阅览
周军锋, 陈伟, 费春苹, 等. BiRch：一种处理k步可达性查询的双向搜索算法[J]. 通信学报, 2015,36(8):50-60.

Jun-feng ZHOU, Wei CHEN, Chun-ping FEI, et al. BiRch:a bidirectional search algorithm for k-step reachability queries[J]. Journal on communications, 2015, 36(8): 50-60.
周军锋, 陈伟, 费春苹, 等. BiRch：一种处理k步可达性查询的双向搜索算法[J]. 通信学报, 2015,36(8):50-60. DOI： 10.11959/j.issn.1000-436x.2015230.

Jun-feng ZHOU, Wei CHEN, Chun-ping FEI, et al. BiRch:a bidirectional search algorithm for k-step reachability queries[J]. Journal on communications, 2015, 36(8): 50-60. DOI： 10.11959/j.issn.1000-436x.2015230.

摘要

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

Abstract

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 different metrics

including indexing time

index size

query processing time

the number of visited vertexes

and scalability.

关键词

Keywords

references

AGRAWAL R , BORGIDA A , JAGADISH H V . Efficient management of transitive relationships in large data and knowledge bases [A ] . Special Interest Group on Management of Data Conference(SIGMOD) [C ] . 1989 . 253 - 262 .

YILDIRIM H , CHAOJI V , ZAKI M J . Grail:scalable reachability index for large graphs [J ] . PVLDB Journal , 2010 , 3 ( 1 ): 276 - 284 .

CHENG J , HUANG S , WU H . TF-label:a topological-folding labeling scheme for reachability querying in a large graph [A ] . Special Interest Group on Management of Data Conference(SIGMOD) [C ] . New York , 2013 . 193 - 204 .

YANO Y , AKIBA T , IWATA Y . Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths [A ] . International Conference on Information and Knowledge Management(CIKM) [C ] . San Francisco,CA,USA , 2013 . 1601 - 1606 .

CHEN Y , CHEN Y . An efficient algorithm for answering graph reachability queries [A ] . IEEE 24th International Conference on Data Engineering(ICDE) [C ] . 2008 . 893 - 902 .

JIN R , RUAN N , DEY S . SCARAB:Scaling reachability computation on large graphs [A ] . Special Interest Group on Management of Data Conference(SIGMOD)[C].Scottsdale . 2012 . 169 - 180 .

TRIßL S , LESER U . Fast and practical indexing and querying of very large graphs [A ] . Special Interest Group on Management of Data Conference(SIGMOD)[C].Beijing,China . 2007 . 845 - 856 .

JIN R , XIANG Y , RUAN N . Efficiently answering reachability queries on very large directed graphs [A ] . Special Interest Group on Management of Data Conference(SIGMOD) [C ] . Vancouver , 2008 .595608.

WANG H , HE H , YANG J . Dual labeling:answering graph reachability queries in constant time [A ] . International Conference on Data Engineering(ICDE) [C ] . Atlanta,GA,USA , 2006 .

CHENG J , YU J X , LIN X . Fast computing reachability labelings for large graphs with high compression rate [A ] . International Conference on Extending Database Technology(EDBT) [C ] . 2008 . 193 - 204 .

VAN SCHAIK S J , DE MOOR O . A memory efficient reachability data structure through bit vector compression [A ] . Special Interest Group on Management of Data Conference(SIGMOD) [C ] . Athens , 2011 . 913 - 924 .

ZHU L , CHOI B , HE B . A uniform framework for ad-hoc indexes to answer reachability queries on large graphs [A ] . International Conference on Database Systems for Advanced Applications(DASFAA) [C ] . Brisbane,Australia , 2009 . 138 - 152 .

CHEN Y , CHEN Y . Decomposing DAGs into spanning trees:a new way to compress transitive closures [A ] . International Conference on Data Engineering(ICDE) [C ] . Hannover,Germany , 2011 . 1007 - 1018 .

李艳 , 孙乐 , 朱怀忠 . 网树求解有向无环图中具有长度约束的简单路径和最长路径问题 [J ] . 计算机学报 , 2012 , 35 ( 10 ): 2194 - 2203 .

LI Y , SUN L , ZHU H Z . A nettree for simple paths with legngth constraint and the longest path in directed acyclic graphs [J ] . Chinese Journal of Computer , 2012 , 35 ( 10 ): 2194 - 2203 .

CHEN L , GUPTA A , KURUL M E . Stack-based algorithms for pattern matching on DAGs [A ] . International Conference on Very Large Data Bases(VLDB) [C ] . Trondheim,Norway , 2005 . 493 - 504 .

AKIBA T , IWATA Y , YOSHIDA Y . Fast exact shortest-path distance queries on large networks by pruned landmark labeling [A ] . Special Interest Group on Management of Data Conference(SIGMOD) [C ] . New York , 2013 . 349 - 360 .

CHENG J , SHANG Z , CHENG H . K-reach:who is in your small world [J ] . PVLDB,Journal , 2012 , 5 ( 11 ): 1292 - 1303 .

CHENG J , SHANG Z , CHENG H . Efficient processing of k-hop reachability queries [J ] . VLDB Journal , 2014 , 23 ( 2 ): 227 - 252 .

浏览量

1264

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据