Top-k correlated subgraph query for data streams

Pan, S; Zhu, X; Fang, M

Top-k correlated subgraph query for data streams

Pan, S

Zhu, X Fang, M

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Pattern Recognition, 2012, pp. 2906 - 2909
Issue Date:: 2012-12-01

Closed Access

	Filename	Description	Size
	06460773.pdf	Published version	282.39 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	Pan, S https://orcid.org/0000-0003-0794-527X	en_US
dc.contributor.author	Zhu, X	en_US
dc.contributor.author	Fang, M	en_US
dc.date.issued	2012-12-01	en_US
dc.identifier.citation	Proceedings - International Conference on Pattern Recognition, 2012, pp. 2906 - 2909	en_US
dc.identifier.isbn	9784990644109	en_US
dc.identifier.issn	1051-4651	en_US
dc.identifier.uri	http://hdl.handle.net/10453/119894
dc.description.abstract	Given a query graph q, correlated subgraph query intends to find graph structures which are mostly correlated to the query q. This problem is fundamental for many pattern recognition applications involving structured data like graphs. Current available studies on correlation mining from graph data are all designed for static datasets. However, in real-life applications, data may arrive continuously in a streaming fashion with high speed. In this paper we investigate the problem of top-k correlated subgraph query over stream. By employing Hoeffding bound into the candidate discovery process and carefully maintaining a candidate list over stream, a novel algorithm, Hoe-PG, is proposed to incrementally identify the top-k correlated subgraphs in a sliding window over stream. Experiments show that the proposed method is several times more efficient than its peer with respect to the runtime and the memory consumption, and is able to maintain high precision and recall for stream-based graph query. © 2012 ICPR Org Committee.	en_US
dc.relation.ispartof	Proceedings - International Conference on Pattern Recognition	en_US
dc.title	Top-k correlated subgraph query for data streams	en_US
dc.type	Conference Proceeding
utslib.for	080109 Pattern Recognition and Data Mining	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	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/Strength - AAI - Advanced Analytics Institute Research Centre
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

Given a query graph q, correlated subgraph query intends to find graph structures which are mostly correlated to the query q. This problem is fundamental for many pattern recognition applications involving structured data like graphs. Current available studies on correlation mining from graph data are all designed for static datasets. However, in real-life applications, data may arrive continuously in a streaming fashion with high speed. In this paper we investigate the problem of top-k correlated subgraph query over stream. By employing Hoeffding bound into the candidate discovery process and carefully maintaining a candidate list over stream, a novel algorithm, Hoe-PG, is proposed to incrementally identify the top-k correlated subgraphs in a sliding window over stream. Experiments show that the proposed method is several times more efficient than its peer with respect to the runtime and the memory consumption, and is able to maintain high precision and recall for stream-based graph query. © 2012 ICPR Org Committee.

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

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