Space efficient mining of multigraph streams

Graham Cormode, S. Muthukrishnan

    Research output: Contribution to conferencePaperpeer-review


    The challenge of monitoring massive amounts of data generated by communication networks has led to the interest in data stream processing. We study streams of edges in massive communication multigraphs, defined by (source, destination) pairs. The goal is to compute properties of the underlying graph while using small space (much smaller than the number of communicants), and to avoid bias introduced because some edges may appear many times, while others are seen only once. We give results for three fundamental problems on multigraph degree sequences: estimating frequency moments of degrees, finding the heavy hitter degrees, and computing range sums of degree values. In all cases we are able to show space bounds for our summarizing algorithms that are significantly smaller than storing complete information. We use a variety of data stream methods: sketches, sampling, hashing and distinct counting, but a common feature is that we use cascaded summaries: nesting multiple estimation techniques within one another. In our experimental study, we see that such summaries are highly effective, enabling massive multigraph streams to be effectively summarized to answer queries of interest with high accuracy using only a small amount of space.

    Original languageEnglish (US)
    Number of pages12
    StatePublished - 2005
    EventTwenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2005 - Baltimore, MD, United States
    Duration: Jun 13 2005Jun 15 2005


    ConferenceTwenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2005
    Country/TerritoryUnited States
    CityBaltimore, MD

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Hardware and Architecture


    Dive into the research topics of 'Space efficient mining of multigraph streams'. Together they form a unique fingerprint.

    Cite this