Distributed top-k aggregation queries at large

Thomas Neumann, Matthias Bender, Sebastian Michel, Ralf Schenkel, Peter Triantafillou, Gerhard WeikumDistributed Parallel Databases 2009 · DOI

Abstract

Distributed top-k aggregation queries are essential for large-scale network monitoring and data analysis. Traditional methods like the Three-Phase Uniform Threshold (TPUT) algorithm suffer from communication bottlenecks and inefficiencies due to uniform thresholding. This paper presents three optimization techniques: hierarchical grouping, adaptive scan depths, and data-adaptive sampling. These methods leverage local data synopses and statistical cost models to significantly reduce query response times and bandwidth consumption. Experimental results across various real-world datasets demonstrate speedups of up to 5x while maintaining high accuracy.

Introduction

In large-scale distributed environments such as sensor networks or global web server clusters, identifying the top-$k$ items by aggregate score is a common but challenging task. A typical query might seek the most frequent URLs accessed across global caches. The baseline approach, TPUT, relies on a central coordinator and uniform thresholds across all nodes. This "flat" model leads to two primary issues: central node congestion and wasted bandwidth on nodes with sparse relevant data.

Optimization Techniques

To address these challenges, we propose a suite of optimizations that transition from a flat, uniform model to a hierarchical, adaptive one.

Hierarchical Grouping

Instead of a star topology, nodes are organized into an operator tree. Intermediate nodes perform partial aggregations, which distributes the bandwidth load and enables parallel processing. The optimal tree structure is determined using dynamic programming for small networks and fast heuristics for larger ones.

Adaptive Scan Depths

Uniform thresholds are inefficient when data distributions vary across nodes. By sharing compact "local synopses" (e.g., histograms), the coordinator can predict the necessary contribution from each node. This allows for deeper scans on data-rich nodes and shallower scans on others, minimizing total data transfer.

Site Sampling

For massive scales involving thousands of nodes, we introduce a sampling dimension. By identifying and querying only a subset of "heavy" nodes likely to contain top results, the system can provide high-quality approximate results significantly faster than exhaustive methods.

Comparison of baseline TPUT with hierarchical grouping, adaptive thresholds, and sampling optimizations.

Evaluation and Key Results

The proposed methods were evaluated using the ns-2 network simulator on three real-world datasets: WorldCup HTTP logs, AOL query logs, and a retail benchmark.

  • Performance Gains: Hierarchical tree structures achieved up to a 4x improvement in response time over flat baselines.
  • Scalability: In a 5,000-node environment, the sampling-based approach was 5x faster than non-sampling methods, achieving 90% recall for top-100 queries.
  • Efficiency: Adaptive thresholds effectively tailored the workload to individual node distributions, drastically reducing unnecessary data transfers.

Discussion and Limitations

The effectiveness of these optimizations relies heavily on local synopses and the assumption of data independence across nodes. While highly effective for monotonic aggregation functions (SUM, MIN, MAX), future work is required to support non-monotonic functions like AVERAGE. Additionally, maintaining hierarchical structures in highly dynamic peer-to-peer environments with frequent node churn remains an open challenge.

Conclusion

By replacing flat communication and uniform thresholds with hierarchical, data-adaptive strategies, distributed top-k queries can scale to thousands of nodes with minimal latency and high accuracy. These optimizations provide a robust framework for efficient global data aggregation in modern distributed systems.

Summary updated

BibTeX
@article{neumann2009distributed,
  author = {Thomas Neumann and Matthias Bender and Sebastian Michel and Ralf Schenkel and Peter Triantafillou and Gerhard Weikum},
  title = {{Distributed top-k aggregation queries at large}},
  journal = {Distributed Parallel Databases},
  year = {2009},
  doi = {10.1007/s10619-009-7041-z},
}
Figure