Answering reachability queries with ordered label constraints over labeled graphs

doi:10.1007/s11704-022-2368-y

Frontiers of Computer Science

2024, Vol. 18

Issue (1): 181601 https://doi.org/10.1007/s11704-022-2368-y

本期目录

Answering reachability queries with ordered label constraints over labeled graphs

Daoliang HE, Pingpeng YUAN(

), Hai JIN

National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science & Technology, Huazhong University of Science and Technology, Wuhan 430074, China

全文: PDF(4670 KB) HTML

Abstract：

Reachability query plays a vital role in many graph analysis tasks. Previous researches proposed many methods to efficiently answer reachability queries between vertex pairs. Since many real graphs are labeled graph, it highly demands Label-Constrained Reachability (LCR) query in which constraint includes a set of labels besides vertex pairs. Recent researches proposed several methods for answering some LCR queries which require appearance of some labels specified in constraints in the path. Besides that constraint may be a label set, query constraint may be ordered labels, namely OLCR (Ordered-Label-Constrained Reachability) queries which retrieve paths matching a sequence of labels. Currently, no solutions are available for OLCR. Here, we propose DHL, a novel bloom filter based indexing technique for answering OLCR queries. DHL can be used to check reachability between vertex pairs. If the answers are not no, then constrained DFS is performed. So, we employ DHL followed by performing constrained DFS to answer OLCR queries. We show that DHL has a bounded false positive rate, and it’s powerful in saving indexing time and space. Extensive experiments on 10 real-life graphs and 12 synthetic graphs demonstrate that DHL achieves about 4.8–22.5 times smaller index space and 4.6–114 times less index construction time than two state-of-art techniques for LCR queries, while achieving comparable query response time. The results also show that our algorithm can answer OLCR queries effectively.

Key words： graph ordered-label-constrained reachability partial index bloom filter query processing

收稿日期: 2022-06-19 出版日期: 2023-02-27

Corresponding Author(s): Pingpeng YUAN

作者简介:

Qingyong Zheng and Ya Gao contributed equally to this work.

引用本文:

. [J]. Frontiers of Computer Science, 2024, 18(1): 181601.
Daoliang HE, Pingpeng YUAN, Hai JIN. Answering reachability queries with ordered label constraints over labeled graphs. Front. Comput. Sci., 2024, 18(1): 181601.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-022-2368-y
https://academic.hep.com.cn/fcs/CN/Y2024/V18/I1/181601

Fig.1

Fig.2

$v$	$L o u t (v)$	$L i n (v)$
$v 1$	$(1, l 1), 2, (2, l 1 l 2), (3, l 1)$ $(4, l 1 l 2 l 4), (5, l 1)$	$2$
$v 2$	$(1, l 2), (2, l 2), 3, (4, l 2 l 4)$ $(5, l 1), (5, l 2 l 3)$	$(2, l 1), 3$
$v 3$	$1, (2, l 2 l 3), (4, l 2$ ? $l 4)$ $(5, l 2), (5, l 3)$	$1, (2, l 1), (3, l 4)$
$v 4$	$1, (5, l 3)$	$1, (2, l 1 l 2), (3, l 2)$
$v 5$	$5$	$(1, l 3), (2, l 1)$ $(3, l 1), (3, l 3 l 4), 5$
$v 6$	$(2, l 3), (4, l 3 l 4), 5$	$(1, l 2), (2, l 1 l 2), (3, l 1 l 2)$ $(3, l 2 l 4), 5, (5, l 2)$
$v 7$	$2, (4, l 4)$	$(1, l 2 l 3), 2, (2, l 1$ ? $l 3)$ $(3, l 2), (5, l 3)$
$v 8$	$4$	$(1, l 2), (2, l 4), (3, l 2 l 4)$ $(3, l 1$ - $l 3), 4, (5, l 2 l 3), (5, l 3 l 4)$
$v 9$	$(1, l 4), (1, l 1 l 3), (2, l 1$ ? $l 3)$ $(2, l 2$ ? $l 4), 3, (4, l 1$ ? $l 3)$ $(4, l 2$ ? $l 4), (5, l 1)$ $(5, l 2 l 4), (5, l 3 l 4)$	$3$
$v 10$	$(1, l 3), (2, l 2 l 3), (4, l 2 l 3)$ $5, (5, l 2)$	$(3, l 1), 5$
$v 11$	$1, (4, l 2)$	$1, (3, l 1 l 3), (5, l 3)$

Tab.1

Dataset	Abbr.	$\| V \|$	$\| E \|$	$\| Σ \|$ labels	Synthetic labels
Robots	RT	1.2K	2.4K	4
Advogato	ADG	5.4K	28K	4
arXiv	AX	34K	417K	8	√
BioGrid	BG	64K	489K	7
StringsAM See string-db.org website.	SAM	6.1K	755K	7
Youtube	YT	15K	3.5M	5
StringsFC	SFC	19K	4.4M	7
webStanford	WS	281K	1.2M	8	√
WebGoogle	WG	916K	3.1M	8	√
CentralUSA See konect.cc/networks/ website.	CU	14M	17M	8	√
FullUSA See konect.cc/networks/ website.	FU	24M	29M	8	√

Tab.2

Tab.3

Name	$\| Σ \| / 4$ or 2			$\| Σ \| / 2$ or 4			$\| Σ \| ? 2$ or 6
Name	LI+	P2H+	DHL	LI+	P2H+	DHL	LI+	P2H+	DHL
RT	0.1	0.2	0.03	0.1	0.17	0.06
ADG	1.05	0.68	0.62	0.45	0.53	0.7
AX	86	2.6	7.4	105	1.8	3.9	191	1.1	1.8
BG	82	1.4	4.9	137	1.0	4.0	181	0.8	1.8
SAM	21.4	0.89	5.9	8.7	0.96	26	21.5	0.76	8.0
YT	106	0.86	90	69	0.91	68
SFC	252	3.4	68	437	2.8	37	275	3.0	39
WS	14	1.3	0.03	123	1.3	0.27	798	1.64	1.28
WG	?	?	0.04	?	?	0.37	?	?	27.8
CU	?	?	0.01	?	?	0.01	?	?	0.02

Tab.4

Name	$\| Σ \| / 4$ or 2			$\| Σ \| / 2$ or 4			$\| Σ \| ? 2$ or 6
Name	LI+	P2H+	DHL	LI+	P2H+	DHL	LI+	P2H+	DHL
RT	0.1	0.09	0.02	0.1	0.23	0.04
ADG	0.25	0.68	0.19	0.32	0.64	0.47
AX	6.6	2.7	2.4	27	2.9	5.7	44	2.5	7.8
BG	6.1	0.9	1.5	15.7	1.3	5.0	26	1.3	5.9
SAM	9.4	1.1	11	13.5	1.3	22	14.7	1.4	23
YT	13.3	0.9	65	16.5	1.2	63
SFC	84.2	5.2	79	107	4.4	80	116	4.6	77
WS	1.7	1.4	0.04	15.8	1.5	0.11	76.5	1.7	0.71
WG	?	?	0.04	?	?	0.06	?	?	7.1
CU	?	?	0.03	?	?	0.03	?	?	0.03

Tab.5

Tab.6

Fig.3

Fig.4

Fig.5

Fig.6

Name	$\| Σ \| / 4$ or 2						$\| Σ \| / 2$ or 4						$\| Σ \| ? 2$ or 6
	LI+		P2H+		DHL+		LI+		P2H+		DHL+		LI+		P2H+		DHL+
	F	R	F	R	F	R	F	R	F	R	F	R	F	R	F	R	F	R
RT	0.47	0.45	0.89	0.41	0.14	0.09	0.29	36	0.42	79	0.15	14.9
ADG	3.2	6.9	2.1	15.3	1.9	5.6	1.2	1.3ms	1.4	2.5ms	1.8	1.9ms
AX	93	?	4.1	705ms	8.4	625ms	125	?	2.9	?	4.9	?	287	?	2.2	?	2.8	?
BG	90	131ms	2.4	25ms	5.7	32ms	845	?	8.1	?	25	?	1.1ms	?	6.7	?	11.5	?
SAM	27	1.2ms	1.9	210	6.9	1.4ms	12	?	1.6	?	29	?	25	?	1.2	?	9.1	?
YT	115	?	1.4	423ms	90	?	174	?	3.1	?	156	?
SFC	265	?	4.3	?	68	?	446	?	3.9	?	37	?	287	?	4.5	?	39	?
WS	98	9.9	11	8.3	0.21	0.23	196	45	2.7	4.2	0.43	0.31	872	?	2.3	49ms	1.4	15.8ms
WG	?	?	?	?	0.28	0.24	?	?	?	?	0.62	0.27	?	?	?	?	27.8	19.2

Tab.7

1	R, Jin H, Hong H, Wang N, Ruan Y Xiang . Computing label-constraint reachability in graph databases. In: Proceedings of 2010 ACM SIGMOD International Conference on Management of Data. 2010, 123−134
2	J, Zhu Z, Nie X, Liu B, Zhang J Wen . Statsnowball: a statistical approach to extracting entity relationships. In: Proceedings of the 18th International Conference on World Wide Web. 2009, 101−110
3	C, Yang G, Liu C, Yan C Jiang . A clustering-based flexible weighting method in AdaBoost and its application to transaction fraud detection. Science China Information Sciences, 2021, 64( 12): 222101
4	J, Cheng S, Huang H, Wu A W C Fu . Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In: Proceedings of 2013 ACM SIGMOD International Conference on Management of Data. 2013, 193−204
5	E, Cohen E, Halperin H, Kaplan U Zwick . Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 2003, 32( 5): 1338–1355
6	R, Jin R, Ning S, Dey J Y Xu . SCARAB: scaling reachability computation on large graphs. In: Proceedings of 2012 ACM SIGMOD International Conference on Management of Data. 2012, 169−180
7	R, Jin Y, Xiang N, Ruan H Wang . Efficiently answering reachability queries on very large directed graphs. In: Proceedings of 2008 ACM SIGMOD International Conference on Management of Data. 2008, 595−608
8	L, Li W, Hua X Zhou . HD-GDD: high dimensional graph dominance drawing approach for reachability query. World Wide Web, 2017, 20( 4): 677–696
9	J, Su Q, Zhu H, Wei J X Yu . Reachability querying: can it be even faster?. IEEE Transactions on Knowledge and Data Engineering, 2017, 29( 3): 683–697
10	H, Wei J X, Yu C, Lu R Jin . Reachability querying: an independent permutation labeling approach. Proceedings of the VLDB Endowment, 2014, 7( 12): 1191–1202
11	H, Wei J X, Yu C, Lu R Jin . Reachability querying: an independent permutation labeling approach. The VLDB Journal, 2018, 27( 1): 1–26
12	P, Yuan Y, You S, Zhou H, Jin L Liu . Providing fast reachability query services with MGTag: a multi-dimensional graph labeling method. IEEE Transactions on Services Computing, 2022, 15( 2): 1000–1011
13	P, Holme J Saramäki . Temporal networks. Physics Reports, 2012, 519( 3): 97–125
14	C, Shi Y, Li J, Zhang Y, Sun P S Yu . A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering, 2017, 29( 1): 17–37
15	Y, Peng Y, Zhang X, Lin L, Qin W Zhang . Answering billion-scale label-constrained reachability queries within microsecond. Proceedings of the VLDB Endowment, 2020, 13( 6): 812–825
16	L, Zou K, Xu J X, Yu L, Chen Y, Xiao D Zhao . Efficient processing of label-constraint reachability queries in large graphs. Information Systems, 2014, 40: 47–66
17	L D J, Valstar G H L, Fletcher Y Yoshida . Landmark indexing for evaluation of label-constrained reachability queries. In: Proceedings of 2017 ACM International Conference on Management of Data. 2017, 345−358
18	R, Jin N, Ruan Y, Xiang H Wang . Path-tree: an efficient reachability indexing scheme for large directed graphs. ACM Transactions on Database Systems, 2011, 36( 1): 7
19	Y, Chen Y Chen . An efficient algorithm for answering graph reachability queries. In: Proceedings of the 24th IEEE International Conference on Data Engineering. 2008, 893−902
20	Schaik S J, Van Moor O De . A memory efficient reachability data structure through bit vector compression. In: Proceedings of 2011 ACM SIGMOD International Conference on Management of Data. 2011, 913−924
21	H, Wang H, He J, Yang P S, Yu J X Yu . Dual labeling: answering graph reachability queries in constant time. In: Proceedings of the 22nd International Conference on Data Engineering (ICDE'06). 2006, 75
22	Y Chen . General spanning trees and reachability query evaluation. In: Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering. 2009, 243−252
23	R, Jin Y, Xiang N, Ruan D Fuhry . 3-HOP: a high-compression indexing scheme for reachability query. In: Proceedings of 2009 ACM SIGMOD International Conference on Management of Data. 2009, 813−826
24	R, Jin G Wang . Simple, fast, and scalable reachability oracle. Proceedings of the VLDB Endowment, 2013, 6( 14): 1978–1989
25	R, Schenkel A, Theobald G Weikum . HOPI: an efficient connection index for complex xml document collections. In: Proceedings of the 9th International Conference on Extending Database Technology. 2004, 237−255
26	J, Cheng J X, Yu X, Lin H, Wang S Y Philip . Fast computation of reachability labeling for large graphs. In: Proceedings of the 10th International Conference on Extending Database Technology. 2006, 961−979
27	J, Cai C K Poon . Path-hop: efficiently indexing large graphs for reachability queries. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010, 119−128
28	A D, Zhu W, Lin S, Wang X Xiao . Reachability queries on large dynamic graphs: a total order approach. In: Proceedings of 2014 ACM SIGMOD International Conference on Management of Data. 2014, 1323−1334
29	S, TrßI U Leser . Fast and practical indexing and querying of very large graphs. In: Proceedings of 2007 ACM SIGMOD International Conference on Management of Data. 2007, 845−856
30	H, Yildirim V, Chaoji M J Zaki . Grail: scalable reachability index for large graphs. Proceedings of the VLDB Endowment, 2010, 3( 1−2): 276–284
31	H, Yıldırım V, Chaoji M J Zaki . Grail: a scalable index for reachability queries in very large graphs. The VLDB Journal, 2012, 21( 4): 509–534
32	S, Seufert A, Anand S, Bedathur G Weikum . FERRARI: flexible and efficient reachability range assignment for graph indexing. In: Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE). 2013, 1009−1020
33	G D, Battista P, Eades R, Tamassia I G Tollis . Graph Drawing: Algorithms for the Visualization of Graphs. New Jersey: Prentice Hall, 1999
34	R R, Veloso L, Cerf W Jr, Meira M J Zaki . Reachability queries in very large graphs: a fast refined online search approach. In: Proceedings of the 17th International Conference on Extending Database Technology. 2014, 511−522
35	N, Sengupta A, Bagchi M, Ramanath S Bedathur . ARROW: approximating reachability using random walks over web-scale graphs. In: Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE). 2019, 470−481
36	S, Wadhwa A, Prasad S, Ranu A, Bagchi S Bedathur . Efficiently answering regular simple path queries on large labeled networks. In: Proceedings of 2019 International Conference on Management of Data. 2019, 1463−1480
37	B H Bloom . Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13( 7): 422–426
38	L, Luo D, Guo R T B, Ma O, Rottenstreich X Luo . Optimizing bloom filter: challenges, solutions, and comparisons. IEEE Communications Surveys & Tutorials, 2019, 21( 2): 1912–1949

[1]

FCS-22368-OF-DH_suppl_1

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed