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 contributionposted on 2021-01-07, 22:17 authored 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.
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.
Pagination15p. (p. 106690-106704)
Rights StatementThe 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.
Science & TechnologyTechnologyComputer Science, Information SystemsEngineering, Electrical & ElectronicTelecommunicationsComputer ScienceEngineeringData streamsgraph streamscorrelated structure pattern queryPearson correlation coefficientFREQUENT ITEMSETSOUTLIER DETECTIONSLIDING WINDOWDISCOVERYCLASSIFIERPAIRS