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

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

摘要/Abstract

摘要：

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

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

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.

Key words: k-step reachability query, bidirectional search, breadth level, topological level

周军锋,陈伟,费春苹,陈子阳. BiRch：一种处理k步可达性查询的双向搜索算法[J]. 通信学报, 2015, 36(8): 50-60.

Jun-feng ZHOU,Wei CHEN,Chun-ping FEI,Zi-yang CHEN. BiRch:a bidirectional search algorithm for k-step reachability queries[J]. Journal on Communications, 2015, 36(8): 50-60.

图/表 8

图1

图2

表1

表2

表3

表4

表5

表6

参考文献 18

[1]	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.
[2]	YILDIRIM H , CHAOJI V , ZAKI M J . Grail:scalable reachability index for large graphs[J]. PVLDB Journal, 2010,3(1): 276-284.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	李艳, 孙乐, 朱怀忠 . 网树求解有向无环图中具有长度约束的简单路径和最长路径问题[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.
[15]	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.
[16]	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.
[17]	CHENG J , SHANG Z , CHENG H . K-reach:who is in your small world[J]. PVLDB,Journal, 2012,5(11): 1292-1303.
[18]	CHENG J , SHANG Z , CHENG H . Efficient processing of k-hop reachability queries[J]. VLDB Journal, 2014,23(2): 227-252.

数据集	\|V\|	\|E\|	indeg_max	outdeg_max
Agrocyc	12 684	13 657	571	5 487
Amaze	3 710	3 947	1 237	1 860
Anthra	12 499	13 327	486	5 400
Arxiv	6 000	66 707	695	173
Citeseer	10 720	44 258	184	57
Ecoo	12 620	13 575	542	5 434
Go	6 793	13 361	6	70
Human	38 811	39 816	553	28 570
Kegg	3 617	4 395	1 234	2 048
Mtbrv	9 602	10 438	467	4 004
Nasa	5 605	6 538	11	30
Pubmed	9 000	40 028	432	87
Vchocyc	9 491	10 345	486	3 916
Xmark	6 080	7 051	192	803
Yago	6 642	42 392	2 370	55
citeseerx05p	1 457 057	3 002 252	53 452	2 774
go-uniprot01p	665 850	4 584 419	1 186 281	170
cit-patent05p	1 671 488	3 303 789	139	128
uniprot22m	1 595 444	1 595 442	1 539 898	1

数据集	GRAIL	k-reach	PLL	BiRch	BiRch-BL	BiRch-BTL
Agrocyc	0.21	10.43	384.28	0.21	1.25	2.26
Amaze	0.13	24.92	59.27	0.13	0.42	0.78
Anthrax	0.22	8.80	367.91	0.22	1.19	2.25
Arxiv	1.63	1 346.71	2 396.37	1.63	2.32	3.97
Citeseer	2.38	253.32	509.18	2.38	2.86	5.40
Ecoo	0.24	14.21	384.10	0.24	1.27	2.45
Go	0.94	52.60	212.77	0.94	1.45	2.43
Human	0.54	41.91	2 532.34	0.54	3.56	6.64
Kegg	0.21	29.72	58.23	0.21	0.49	0.90
Mtbrv	0.20	8.96	234.67	0.20	0.99	1.87
Nasa	0.36	38.08	131.15	0.36	0.91	1.33
Pubmed	1.39	100.90	517.63	1.39	2.25	4.21
Vchocyc	0.20	9.27	232.18	0.20	0.97	1.74
Xmark	0.27	37.01	141.35	0.27	1.10	1.57
Yago	1.00	13.83	222.66	1.00	1.25	2.36
citeseerx05p	135.49	4 358.08	—	135.49	428.84	784.50
go-uniprot01p	71.85	553 799	—	71.85	178.69	385.30
cit-patent05p	298.31	656.05	—	298.31	815.96	1 402.06
uniprot22m	71.66	359.23	—	71.66	223.88	409.93

数据集	GRAIL	k-reach	PLL	BiRch	BiRch-BL	BiRch-BTL
Agrocyc	0.32	0.15	0.63	0.32	0.37	0.42
Amaze	0.08	0.18	0.17	0.08	0.09	0.11
Anthrax	0.32	0.15	0.62	0.32	0.36	0.42
Arxiv	0.12	19.00	2.85	0.12	0.14	0.17
Citeseer	0.24	0.84	1.15	0.24	0.28	0.33
Ecoo	0.32	0.16	0.63	0.32	0.36	0.43
Go	0.16	0.23	0.57	0.16	0.18	0.22
Human	1.12	0.46	1.95	1.12	1.23	1.42
Kegg	0.08	0.22	0.17	0.08	0.09	0.11
Mtbrv	0.23	0.12	0.48	0.23	0.27	0.34
Nasa	0.13	0.20	0.35	0.13	0.15	0.15
Pubmed	0.21	1.20	1.25	0.21	0.24	0.28
Vchocyc	0.23	0.12	0.47	0.23	0.26	0.31
Xmark	0.14	0.30	0.37	0.14	0.16	0.19
Yago	0.13	0.09	0.61	0.13	0.15	0.18
citeseerx05p	52.09	44.75	—	52.09	57.78	65.11
go-uniprot01p	17.04	147.46	—	17.04	19.64	22.82
cit-patent05p	60.26	23.51	—	60.26	66.78	74.78
uniprot22m	41.92	19.19	—	41.92	46.60	52.83

数据集	GRAIL	k-reach	PLL	BiRch	BiRch-BL	BiRch-BTL
Agrocyc	1.71	1.47	21.11	0.84	0.81	0.78
Amaze	82.42	2.83	12.36	2.59	2.30	2.16
Anthrax	1.58	1.32	21.46	0.80	0.79	0.77
Arxiv	11 115.90	36.72	212.76	612.38	606.12	447.07
Citeseer	14.36	12.27	50.04	8.25	8.04	6.01
Ecoo	1.90	1.68	20.34	0.85	0.81	0.80
Go	3.12	6.72	27.53	2.81	2.59	2.49
Human	1.94	1.56	30.57	0.81	0.81	0.81
Kegg	107.15	3.41	12.51	2.68	2.54	2.41
Mtbrv	1.56	1.62	18.10	0.82	0.80	0.78
Nasa	2.48	4.34	18.20	1.96	1.90	1.87
Pubmed	13.43	10.48	58.31	6.56	6.48	5.39
Vchocyc	1.58	1.49	17.94	0.81	0.80	0.80
Xmark	14.71	3.94	17.74	2.31	2.28	2.24
Yago	3.61	2.87	31.27	2.37	2.32	1.43
citeseerx05p	10.71	903.82	—	10.37	10.03	6.24
go-uniprot01p	7.88	17 205.10	—	8.29	7.95	4.87
cit-patent05p	1.96	80.75	—	2.63	2.52	2.16
uniprot22m	3.34	109.22	—	2.56	2.47	0.98

数据集	GRAIL	k-reach	BiRch	BiRch-BL	BiRch-BTL
Agrocyc	142 386	110 749	100 345	100 250	100 238
Amaze	16 351 674	149 480	138 656	133 410	132 312
Anthrax	138 568	109 644	100 308	100 206	100 200
Arxiv	1 929 333 067	499 104	80 738 948	75 887 342	55 008 203
Citeseer	1 294 447	330 228	479 353	470 275	328 549
Ecoo	142 846	110 792	100 368	100 301	100 290
Go	248 098	208 329	135 048	125 114	115 006
Human	170 257	103 908	100 031	100 014	100 014
Kegg	21 569 254	163 295	146 498	137 430	136 138
Mtbrv	143 470	112 730	100 724	100 535	100 505
Nasa	134 389	159 186	114 462	113 665	112 312
Pubmed	1 507 629	349 759	412 416	410 508	312 118
Vchocyc	143 824	113 120	100 465	100 349	100 344
Xmark	1 904 054	157 893	120 736	119 064	117 099
Yago	372 986	172 977	139 888	133 178	125 328
citeseerx05p	841 455	1 589 887	349 634	349 465	244 080
go-uniprot01p	366 756	731 755	254 863	247 256	180 385
cit-patent05p	118 752	183 404	114 805	114 793	106 802
uniprot22m	151 027	2 018 312	101 077	101 077	100 027