Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets

Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel ThorupPVLDB 2009 · DOI · OpenReview

TL;DR

This paper introduces a novel framework for summarizing massive, unaggregated datasets, crucial for applications like network traffic analysis. Their "Summarization Algebra" allows for composable, scalable, and accurate weight summaries, outperforming existing methods by a significant margin, especially in challenging scenarios.

What Problem Does This Paper Address?

Imagine you have a colossal dataset where individual data points (like network packets) are associated with keys (like IP addresses or flow IDs), but the same key can appear many times. You want to efficiently summarize this data to answer queries about the total "weight" (e.g., bytes transferred) for arbitrary subsets of keys. The challenge is that traditional aggregation methods (summing up all weights for a key first) are infeasible in high-speed environments due to memory and processing constraints. Existing sampling techniques often struggle with unaggregated data or lack the flexibility to handle complex queries and network topologies. This paper tackles the problem of creating accurate, resource-efficient summaries for these unaggregated, high-volume data streams, especially within hierarchical data processing structures (Information Flow Trees or IFTs).

Methods

The core contribution is a Summarization Algebra (SA), a framework that breaks down the summarization problem into smaller, composable steps. Each node in an IFT (representing a processing stage) performs an independent summarization of the data it receives from its children. The key innovation is using VAROPT (Variance Optimal) as the primitive summarization technique for aggregated data. When applied to unaggregated data within the SA framework, this yields SA[VAROPT].

Key aspects of their approach include:

  • Composable and Scalable: The SA allows summaries to be built up hierarchically, making it suitable for distributed systems and large-scale data processing.
  • Unbiased Estimators: The summaries provide unbiased estimates for arbitrary subset sums, meaning they don't systematically over or undercount.
  • Modular Design: The framework is modular, allowing different summarization algorithms to be plugged in at each stage.
  • Streaming Modularity: The scheme transparently handles streaming data, where data arrives continuously.
  • Flexibility: It can handle multiple weight functions (e.g., bytes and packet counts) and even negative weights.
  • Efficient Implementation: They developed a specialized implementation of SA[VAROPT] for streams that achieves near-constant time per data point on average.

Datasets

The authors evaluated their methods on a variety of datasets:

  • Synthetic Data:
    • Pareto Distributions: Used to model skewed data distributions, with varying parameters to test robustness.
  • Netflix Prize Data: A large dataset of movie ratings, treated as an unaggregated stream.
  • Real-World Data:
    • IP Packet Header Streams: Two datasets from campus and peering network links, containing anonymized flow metadata and packet byte weights. These were used to simulate both stream and distributed server scenarios.

Key Insights and Ideas

  • The "Merge Before Summarizing" Rule: For IFTs, it's generally more beneficial to merge data from children before applying a summarization step, rather than summarizing each child's data independently and then merging summaries. This leads to more accurate results.
  • No Perfect Solution for Unaggregated Streams: The paper proves that no streaming algorithm can achieve the absolute minimum variance for unaggregated data, highlighting the inherent trade-off.
  • Progressive Accuracy: SA[VAROPT] offers a desirable property: as the input data becomes "more aggregated" (fewer unique keys), the estimator variance gets progressively closer to the optimal achievable variance.
  • Significant Gains over Existing Methods: Their approach consistently outperforms established methods like ASH and ANF, especially in scenarios with highly skewed data or complex network structures.

Key Results

  • Accuracy Improvements: SA[VAROPT] demonstrated substantial improvements in accuracy (lower variance) compared to ASH and ANF. For instance, in distributed server scenarios, SAVAROPT achieved 2-10 fold lower variance than ANF. In stream scenarios, SAVAROPT showed 10%-40% smaller variance than ASH.
  • Near-Optimal Performance: On real-world datasets, SA[VAROPT] was often within a few percent of the theoretical optimum achievable with fully aggregated data, and in some cases, within a fraction of a percent.
  • Efficiency: The specialized implementation of SA[VAROPT] for streams achieves amortized O(log k) time per data point, with practical performance often closer to O(1).

Limitations and Future Work

  • Theoretical vs. Practical Optimality: While SA[VAROPT] is highly accurate, it doesn't achieve the theoretical variance optimality of VAROPT on fully aggregated data. The paper acknowledges this cost of not aggregating.
  • Conjecture on Competitive Ratio: The authors conjecture that the competitive ratio of SA[VAROPT] (the ratio of its variance to the optimal variance) is bounded by a constant, suggesting its performance scales well.
  • Signed Weights and Multiple Objectives: The paper discusses extensions for handling signed weights and multiple weight functions (like packet counts and byte counts simultaneously), suggesting these are areas for further exploration.
  • Information Flow DAGs: The framework can be extended to Directed Acyclic Graphs (DAGs) for more complex information flow scenarios, which is left for future work.

Summary updated

BibTeX
@article{cohen2009composable,
  author = {Edith Cohen and Nick G. Duffield and Haim Kaplan and Carsten Lund and Mikkel Thorup},
  title = {{Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687677},
}
Figure