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: hbecfd092b55eaf6c
Venue: PODS
Year: 2004
Pagerank: 0.00010665845
Overall Rank: 1,434 | 90.37%
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
456	Mergeable Summaries	2012	PODS	0.0001791284
1,066	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012192801
1,769	Improving the Performance of List Intersection	2009	VLDB	9.6869284e-05
2,124	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	9.0056375e-05
2,359	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.5813849e-05
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4253671e-05
3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.104636e-05
4,796	Rethinking Data Management for Storage-centric Sensor Networks	2007	CIDR	6.4114857e-05
5,327	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.1783009e-05
6,315	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.8161255e-05
7,016	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.6206282e-05
7,168	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.5947893e-05
7,431	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.5293382e-05
7,916	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4276156e-05
8,170	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.3844369e-05
9,539	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.1621607e-05
9,890	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.1149505e-05
11,878	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.9793485e-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,955	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD
2	2,359	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB
3	343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB
4	9,334	Efficient Gossip-Based Aggregate Computation	2006	PODS
5	1,470	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
6	2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
7	2,124	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD
8	5,698	Approximate Quantiles and the Order of the Stream	2006	PODS
9	5,382	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD
10	6,315	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD