Sampling Based Algorithms for Quantile Computation in Sensor Networks

Summary: Sampling-based algorithm for approximate quantiles in sensor networks, enabling compact in-network quantile summaries beyond simple aggregates. Total communication O(sqrt(k h)/epsilon) with h the routing-tree height; experiments show 10–100x fewer transmissions at similar accuracy, with no increase in max-node load. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4428
Venue: SIGMOD
Year: 2011
Pagerank: 5.0413486e-05
Overall Rank: 6,495 | 54.82%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,313	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.2381634e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
4,190	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.3739017e-05
5,909	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2769377e-05
8,062	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	4.5943269e-05
11,371	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
885	Query Processing for Sensor Networks	2003	CIDR	0.00015646925
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
1,566	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00011343771
2,178	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	9.3559565e-05
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
5,488	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD	5.4782627e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022221803
1,640	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.0001104808
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
12,338	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.1945683e-05
11,371	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.1945683e-05
5,488	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD	5.4782627e-05
2,178	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	9.3559565e-05
4,031	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5121141e-05
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
1,566	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00011343771