Approximating Median Absolute Deviation with Bounded Error

Summary: Introduces OP-MAD, a fully mergeable, one-pass approximate MAD with (epsilon,1)-bounded error via a compact sketch. TP-MAD uses at most two passes with O(n + m log m) time and O(m) space, delivering large memory savings and Spark/Structured Streaming scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12391
Venue: VLDB
Year: 2021
Pagerank: 5.1725247e-05
Overall Rank: 11,509 | 20.02%
DOI: 10.14778/3476249.3476266

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,000	Apache IoTDB: A Time Series Database for IoT Applications	2023	SIGMOD	7.0402889e-05
9,253	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	5.3572577e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	5.1725247e-05
10,399	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	5.1725247e-05
11,252	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036461682
447	Mergeable Summaries	2012	PODS	0.00018364636
1,139	Structured Streaming: A Declarative API for Real-Time Applications in Apache Spark	2018	SIGMOD	0.0001209681
2,417	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	8.6803686e-05
2,698	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	8.2943671e-05
5,465	TcpRT: Instrument and Diagnostic Analysis System for Service Quality of Cloud Databases at Massive Scale in Real-time	2018	SIGMOD	6.276117e-05
6,064	SCREEN: Stream Data Cleaning under Speed Constraints	2015	SIGMOD	6.0519891e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,917	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	5.242442e-05
3,240	Real-Time Distance-Based Outlier Detection in Data Streams	2021	VLDB	7.6784549e-05
11,470	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	5.1725247e-05
2,184	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	9.0601412e-05
5,556	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.2357201e-05
4,129	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.945332e-05
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036461682
4,425	Relative Error Streaming Quantiles	2021	PODS	6.7704846e-05
258	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023249876
11,252	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	5.1725247e-05