Query-friendly compression of graph streams

摘要: We study the problem of synopsis construction massive graph streams arriving in real-time. Many graphs such as those formed by activity on social networks, communication and telephone networks are defined dynamically rapid edge a domain nodes. In these streams, it is often not possible to estimate frequency individual items (e.g., edges, nodes) with complete accuracy. Nevertheless, sketch-based stream summaries Count-Min can preserve information high-frequency reasonable However, sketch lose underlying structure unless one keeps about start end nodes all which prohibitively expensive. For example, existing methods identify but they unable answer more complex structural queries reachability edges. To this end, we design 3-dimensional sketch, gMatrix that summarizes real-time, while also retaining behavior dataset. demonstrate how gMatrix, coupled onetime reverse hash mapping, able important properties, e.g., over high edges an online manner theoretical performance guarantees. Our experimental results using large-scale attest capable answering both frequency-based accuracy efficiency.