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.00010647197
Overall Rank: 1,438 | 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
452	Mergeable Summaries	2012	PODS	0.00018032092
1,070	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.0001215545
1,737	Improving the Performance of List Intersection	2009	VLDB	9.7383962e-05
2,130	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD	8.9875498e-05
2,364	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.5549846e-05
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.0967962e-05
4,822	Rethinking Data Management for Storage-centric Sensor Networks	2007	CIDR	6.3874063e-05
5,336	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.1613661e-05
6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.7992155e-05
7,037	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.5993909e-05
7,192	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.5736733e-05
7,415	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5160692e-05
7,435	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.5132769e-05
7,935	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4071076e-05
9,574	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.1428165e-05
9,931	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.0956239e-05
11,928	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.9605343e-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,976	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD
2	2,364	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,369	Efficient Gossip-Based Aggregate Computation	2006	PODS
5	1,471	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
6	2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
7	2,130	Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams	2005	SIGMOD
8	5,712	Approximate Quantiles and the Order of the Stream	2006	PODS
9	5,411	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD
10	6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD