Power-Conserving Computation of Order-Statistics over Sensor Networks

Summary: First distributed, power-balanced algorithms for sensor-network order-statistics minimizing per-node communication to extend network lifetime. ε-approx quantiles: O((log^2 n)/ε) values per sensor (topology-independent); exact order-statistics in O(log^2 n); improves when height h << n; uses decomposable aggregates. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1329
Venue: PODS
Year: 2004
Pagerank: 0.00010890603
Overall Rank: 1,400 | 90.40%
DOI: 10.1145/1055558.1055597

Incoming Non-self Citations Over Time

Authors

1. Michael B. Greenwald (University of Pennsylvania)
2. Sanjeev Khanna (University of Pennsylvania)

BibTeX Citation

@inproceedings{greenwald_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Power-Conserving Computation of Order-Statistics over Sensor Networks}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055597},
        doi = {10.1145/1055558.1055597},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Greenwald, Michael B. and Khanna, Sanjeev},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
451	Mergeable Summaries	2012	PODS	0.00018151445
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05
2,090	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	9.1894752e-05
2,340	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.7246796e-05
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
4,698	Rethinking Data Management for Storage-centric Sensor Networks	2007	CIDR	6.5569539e-05
5,216	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.3121293e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05
6,871	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.7496345e-05
7,027	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.7231968e-05
7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.6560822e-05
7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.5521918e-05
8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5080221e-05
9,406	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.2751448e-05
9,718	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.2323504e-05
11,569	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,795	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD
2	2,340	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB
3	337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB
4	9,161	Efficient Gossip-Based Aggregate Computation	2006	PODS
5	1,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
6	2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
7	2,090	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD
8	5,604	Approximate Quantiles and the Order of the Stream	2006	PODS
9	5,260	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD
10	6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD