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

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

Abstract

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

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.

Figures/Tables 8

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	\|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

BiRch:a bidirectional search algorithm for k-step reachability queries

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 18

Related Articles 0

Metrics

Recommended 0

数据集	k=2	k=3	k=4	k=5	k=6	k=7	k=8	k=9	k=10
uniprot22m	0.82	0.81	0.81	0.81	0.81	0.81	0.81	0.81	0.82
Ecoo	0.82	0.82	0.81	0.80	0.80	0.80	0.80	0.80	0.80
cit-patent05p	1.58	1.55	1.51	1.53	1.50	1.53	1.56	1.55	1.56
Pubmed	3.49	4.54	5.41	5.81	5.84	5.91	5.90	5.93	5.93
Yago	1.47	1.54	1.55	1.54	1.55	1.57	1.57	1.57	1.57
Arxiv	14.59	57.79	177.61	436.53	734.74	779.13	934.02	980.15	1061