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: 12390
Venue: VLDB
Year: 2021
Pagerank: 4.1945683e-05
Overall Rank: 11,505 | 19.97%
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
3,967	Apache IoTDB: A Time Series Database for IoT Applications	2023	SIGMOD	6.5796647e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
10,388	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1945683e-05
11,250	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.1945683e-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
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
402	Mergeable Summaries	2012	PODS	0.00024196343
1,548	Structured Streaming: A Declarative API for Real-Time Applications in Apache Spark	2018	SIGMOD	0.00011431383
2,914	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	7.9118579e-05
2,953	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8267643e-05
5,732	TcpRT: Instrument and Diagnostic Analysis System for Service Quality of Cloud Databases at Massive Scale in Real-time	2018	SIGMOD	5.3501728e-05
6,583	SCREEN: Stream Data Cleaning under Speed Constraints	2015	SIGMOD	5.0027988e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,924	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2544238e-05
3,468	Real-Time Distance-Based Outlier Detection in Data Streams	2021	VLDB	7.0686044e-05
11,467	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	4.1945683e-05
2,404	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8837279e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
4,083	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4638932e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
11,250	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.1945683e-05