Path-based holistic detection plan for multiple patterns in distributed graph frameworks

Gao, J; Liu, Y; Zhou, C; Yu, JX

Path-based holistic detection plan for multiple patterns in distributed graph frameworks

Gao, J Liu, Y Zhou, C Yu, JX

Permalink

Publication Type:: Journal Article
Citation:: VLDB Journal, 2017, 26 (3), pp. 327 - 345
Issue Date:: 2017-06-01

Closed Access

	Filename	Description	Size
	Gao2017_Article_Path-basedHolisticDetectionPla.pdf	Published Version	1.23 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Gao, J	en_US
dc.contributor.author	Liu, Y	en_US
dc.contributor.author	Zhou, C	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.date.issued	2017-06-01	en_US
dc.identifier.citation	VLDB Journal, 2017, 26 (3), pp. 327 - 345	en_US
dc.identifier.issn	1066-8888	en_US
dc.identifier.uri	http://hdl.handle.net/10453/126868
dc.description.abstract	© 2017, Springer-Verlag Berlin Heidelberg. Multiple pattern detection is needed in applications like disease analysis over gene networks, bug detection in program flow networks. This paper takes pattern detection to investigate the evaluation and optimization of multiple jobs in existing distributed graph processing frameworks. The evaluation plan for multiple pattern detection should be parallelizable and can capture and reuse the shared parts among pattern queries easily. In this paper, we design a path-based holistic plan for multiple pattern queries. Specifically, (1) we design a path-based edge-covered plan for an individual pattern. The paths in the plan can be easily captured and reused among different queries. Additionally, the evaluation plan is fully parallelizable, in which each data vertex performs necessary join operations independently during exploring graph. (2) We extend the individual plan to a holistic evaluation plan for multiple queries, whose results are equivalent to those of individual queries. The plan reduces the overall cost by finding frequent paths among queries and reusing the shared part in the holistic plan. (3) We devise various optimization strategies over the holistic plan. The experimental studies, conducted on Giraph, illustrate the high effectiveness of our holistic approaches.	en_US
dc.relation.ispartof	VLDB Journal	en_US
dc.relation.isbasedon	10.1007/s00778-016-0452-3	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Path-based holistic detection plan for multiple patterns in distributed graph frameworks	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	26	en_US
utslib.for	0804 Data Format	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	0806 Information Systems	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access
pubs.issue	3	en_US
pubs.publication-status	Published	en_US
pubs.volume	26	en_US

Abstract:

© 2017, Springer-Verlag Berlin Heidelberg. Multiple pattern detection is needed in applications like disease analysis over gene networks, bug detection in program flow networks. This paper takes pattern detection to investigate the evaluation and optimization of multiple jobs in existing distributed graph processing frameworks. The evaluation plan for multiple pattern detection should be parallelizable and can capture and reuse the shared parts among pattern queries easily. In this paper, we design a path-based holistic plan for multiple pattern queries. Specifically, (1) we design a path-based edge-covered plan for an individual pattern. The paths in the plan can be easily captured and reused among different queries. Additionally, the evaluation plan is fully parallelizable, in which each data vertex performs necessary join operations independently during exploring graph. (2) We extend the individual plan to a holistic evaluation plan for multiple queries, whose results are equivalent to those of individual queries. The plan reduces the overall cost by finding frequent paths among queries and reusing the shared part in the holistic plan. (3) We devise various optimization strategies over the holistic plan. The experimental studies, conducted on Giraph, illustrate the high effectiveness of our holistic approaches.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/126868