Continuous top-k query for graph streams

In this paper, we propose to query correlated graphs in a data stream scenario, where an algorithm is required to retrieve the top k graphs which are mostly correlated to a query graph q. Due to the dynamic changing nature of the stream data and the inherent complexity of the graph query process, treating graph streams as static datasets is computationally infeasible or ineffective. In the paper, we propose a novel algorithm, Hoe-PGPL, to identify top-k correlated graphs from data stream, by using a sliding window which covers a number of consecutive batches of stream data records. Our theme is to employ Hoeffding bound to discover some potential candidates and use two level candidate checking (one corresponding to the whole sliding window level and one corresponding to the local data batch level) to accurately estimate the correlation of the emerging candidate patterns, without rechecking the historical stream data. Experimental results demonstrate that the proposed algorithm not only achieves good performance in terms of query precision and recall, but also is several times, or even an order of magnitude, more efficient than the straightforward algorithm with respect to the time and the memory consumption. Our method represents the first research endeavor for data stream based top-k correlated graph query.

• Publication year

  2012

• Venue

  International Conference on Information and Knowledge Management

• Publication date

  2012-10-29

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/2396761.2398717
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Top-k Correlative Graph Mining

  2009influential reference
• Correlated pattern mining in quantitative databases

  2008cited by this paper
• Volatile correlation computation: a checkpoint view

  2008cited by this paper
• Correlation search in graph databases

  2007influential reference
• Probability Inequalities for Sums of Bounded Random Variables

  1994influential reference
• The complexity of theorem-proving procedures

  1971cited by this paper
• Probability inequalities for sum of bounded random variables

  1963influential reference

• Searching Correlated Patterns From Graph Streams

  2020cites this paper
• Efficient Continuous Multi-Query Processing over Graph Streams

  2019cites this paper
• Event pattern discovery by keywords in graph streams

  2017cites this paper
• Sampling for Approximate Bipartite Network Projection

  2017cites this paper
• Estimating Node Similarity by Sampling Streaming Bipartite Graphs

  2017cites this paper
• Link prediction in graph streams

  2016cites this paper
• Towards Publish/Subscribe Functionality on Graphs

  2016cites this paper
• Correlated subgraph search for multiple query graphs in graph streams

  2015cites this paper
• Complex graph stream mining

  2015cites this paper
• Continuous similarity search for evolving queries

  2015cites this paper
• Mining Top-k Minimal Redundancy Frequent Patterns over Uncertain Databases

  2015cites this paper