Searching correlated patterns from graph streams

© 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.