Toward query-friendly compression of rapid graph streams

摘要: We study the problem of summary 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, sketches 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 three-dimensional sketch, gMatrix that summarizes time, while also retaining behavior dataset. demonstrate how gMatrix, coupled one-time reverse hash mapping, able important properties, e.g., over edges an online manner theoretical performance guarantees. Our experimental results using large-scale attest capable answering both frequency-based high accuracy efficiency.