Efficient Gossip-Based Aggregate Computation

Summary: Gossip scheme to compute MIN/MAX/SUM/AVG/RANK w.h.p. on n nodes using O(n log log n) messages and O(log n log log n) rounds. First to beat the O(n log n) message bound, trading a slight round increase for large message savings to cut congestion and energy in sensor/wireless networks. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1402
Venue: PODS
Year: 2006
Pagerank: 5.3111776e-05
Overall Rank: 9,161 | 37.15%
DOI: 10.1145/1142351.1142395

Incoming Non-self Citations Over Time

Authors

1. Srinivas Kashyap (AT&T; University of Maryland)
2. Supratim Deb (AT&T)
3. K. V. M. Naidu (AT&T)
4. Rajeev Rastogi (AT&T)
5. Anand Srinivasan (AT&T)

BibTeX Citation

@inproceedings{kashyap_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Efficient Gossip-Based Aggregate Computation}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142395},
        doi = {10.1145/1142351.1142395},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kashyap, Srinivas and Deb, Supratim and Naidu, K. V. M. and Rastogi, Rajeev and Srinivasan, Anand},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.6560822e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
765	Query Processing for Sensor Networks	2003	CIDR	0.00014217472
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB
2	4,332	The Price of Validity in Dynamic Networks	2004	SIGMOD
3	1,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
4	12,293	Ratio Threshold Queries over Distributed Data Sources	2013	VLDB
5	2,090	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD
6	11,562	MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area	2022	SIGMOD
7	5,260	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD
8	7,641	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD
9	6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD
10	1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS