Taming verification hardness: An efficient algorithm for testing subgraph isomorphism

Shang, H; Zhang, Y; Lin, X; Yu, JX

Taming verification hardness: An efficient algorithm for testing subgraph isomorphism

Shang, H Zhang, Y

Lin, X Yu, JX

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the VLDB Endowment, 2008, 1 (1), pp. 364 - 375
Issue Date:: 2008-01-01

Closed Access

	Filename	Description	Size
	2013005473OK.pdf		604.31 kB	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	Shang, H	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.date.issued	2008-01-01	en_US
dc.identifier.citation	Proceedings of the VLDB Endowment, 2008, 1 (1), pp. 364 - 375	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28968
dc.description.abstract	Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering-and-verification to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques. © 2008 VLDB Endowment.	en_US
dc.relation.ispartof	Proceedings of the VLDB Endowment	en_US
dc.relation.isbasedon	10.14778/1453856.1453899	en_US
dc.title	Taming verification hardness: An efficient algorithm for testing subgraph isomorphism	en_US
dc.type	Conference Proceeding
utslib.citation.volume	1	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	0807 Library and Information Studies	en_US
dc.location.activity	Auckland, New Zealand	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
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.issue	1	en_US
pubs.publication-status	Published	en_US
pubs.volume	1	en_US

Abstract:

Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of filtering-and-verification to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques. © 2008 VLDB Endowment.

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

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