La Trobe

File(s) stored somewhere else

Please note: Linked content is NOT stored on La Trobe and we can't guarantee its availability, quality, security or accept any liability.

Searching correlated patterns from graph streams

journal contribution
posted on 07.01.2021, 22:17 by Ming Jin, Mei Li, Yu Zheng, Lianhua ChiLianhua Chi
© 2013 IEEE. Mining the correlation has attracted widespread attention in the research community because of its advantages in understanding the dependencies between objects. In this paper, a correlated graph pattern searching scheme has been proposed, that is, provided with a query g as a structured pattern (i.e., a graph), our algorithm is capable of retrieving the top- k graphs that most likely correlated with g. Traditional methods treat graph streams as static records, which is computational infeasible or ineffective because of the complexity of searching correlated patterns in a dynamic graph stream. In this paper, by relying on sliding windows to separate graph streams in chunks, we propose a Hoe-PGPL algorithm to handle the top- k correlated patterns searching from a dynamic perspective. Our algorithm applies Hoeffding bound and two-level (Sliding window level and local batch level) candidate inspection to discover potential graph candidates and determine the similarity of these candidates without double-checking the previous stream. Theoretical analysis shows that our method can guarantee the quality of the returned answers, and our experiments also present that Hoe-PGPL has an excellent performance with aspects of precision, recall, runtime, and resource consumption.

Funding

This work was supported in part by the Fundamental Research Funds for the Central Universities under Grant 2452018147, in part by the Doctoral Scienti~c Research Foundation under Grant Z109021709, and in part by the Key Research and Development Program of Shaanxi under Grant 2019ZDLNY07-06-01.

History

Publication Date

18/06/2020

Journal

IEEE Access

Volume

8

Pagination

15p. (p. 106690-106704)

Publisher

IEEE

ISSN

2169-3536

Rights Statement

The Author reserves all moral rights over the deposited text and must be credited if any re-use occurs. Documents deposited in OPAL are the Open Access versions of outputs published elsewhere. Changes resulting from the publishing process may therefore not be reflected in this document. The final published version may be obtained via the publisher’s DOI. Please note that additional copyright and access restrictions may apply to the published version.