Data Quality Profiling at Scale with Progressive Sampling: A Benchmark for Data-Centric AI Pipelines Laure Berti-Équille[0000−0002−8046−0570]
arXiv:2607.25356v1 [cs.DB] 28 Jul 2026
IRD, ESPACE-DEV, 500, rue Jean-François Breton, 34093 Montpellier, France [email protected]
Abstract. Systematic data quality profiling – computing missing-value rates, duplicate fractions, outlier densities, and functional-dependency violations – is foundational for data-centric AI pipelines, yet exhaustive scans over millions of rows are prohibitively slow for near-real-time monitoring. Progressive sampling is the standard lightweight alternative; the key open question is which strategy best preserves profile fidelity at scale. We benchmark nine progressive sampling strategies – blind (random uniform, geometric, Yamane, cluster) and proxy-guided (Metropolis-Hastings, DAG, stratified by column type or quality score, importance-weighted)– on three real-world datasets (NYC 311, NYPD arrests, UCI Adult; up to 500K rows), an IoT sensor stream (2.3M rows), two ultra-large real datasets including the Ultra-Marathon Running dataset [18] (up to 7.4M rows), and synthetic data scaled to 5 × 106 rows. Contrary to the common assumption that exploiting dependency structure sharpens profile estimates, blind representative samplers dominate uniformly. At a 5% budget, random uniform achieves 0.49% mean relative error on NYC 311; DAG-guided MCMC yields 19.5% (≈40× worse at this budget), and across all real datasets DAG is 11–49× worse (Wilcoxon W = 0, p = 0.002, n = 9 independent pairs). Cluster sampling matches random uniform (MRE 0.110 vs. 0.111) with no added complexity; proxyguided methods share the same failure mode as DAG (MRE 0.20–0.35). At scale, random uniform is near-linear (O(N 0.964 )) while DAG is superlinear (O(N 1.272 )), running 28–47× slower on ultra-large data with 6× worse accuracy. Root-cause analysis identifies an IQR proxy mismatch: proxy-guided samplers over-pursue numeric outliers, while quality defects concentrate in categorical columns invisible to the proxy. The actionable finding is that representativeness, not domain knowledge, determines sampler quality – schema-free random uniform or cluster sampling suffices for production-grade quality profiling at scale. Keywords: Data-centric AI · Data quality profiling · Progressive sampling · MCMC sampling · Benchmark · Big data
2
L. Berti-Équille
1
Introduction
Data quality profiling is a foundational stage in data-centric AI (DC-AI) pipelines: computing indicators such as missing-value rates, duplicate fractions, and outlier densities over large tabular datasets is a prerequisite for downstream analytics, model training, and regulatory compliance [2,14]. Administrative datasets in particular (such as the available US 311 service requests, arrest records, social registries) routinely exceed hundreds of thousands to millions of rows, are updated continuously, and carry quality deficiencies that are heterogeneous across columns and non-stationary over time. Exhaustive profiling at this scale is expensive: a full scan of a 5M-row table to recompute a suite of quality indicators may take tens of seconds to minutes per refresh cycle, making real-time or nearreal-time monitoring impractical. Data Quality Profiling as a DC-AI gate. In the DC-AI paradigm, model quality is bounded by data quality, and profiling is the gate that determines whether a dataset is fit for training, evaluation, or serving [19,33,31]. Production DC-AI pipelines are cyclic: data is ingested, profiled, curated (cleaned or filtered based on the profile), used for model training or inference, then monitored for distributional drift before the loop repeats. At each iteration, the profiling step must not become a bottleneck—a pipeline ingesting 500K rows per hour cannot afford a full-scan profiler with a 30-second per-cycle latency. Progressive sampling breaks this bottleneck by trading a controlled accuracy loss for a proportional reduction in scan cost. The central engineering question is which sampling strategy achieves the best accuracy–cost trade-off without requiring schema metadata or handcrafted dependency graphs that are expensive to maintain as data evolves. Our benchmark is the first systematic answer to this question in sampling strategies ranging from blind draws to MCMC-guided, stratified, and importance-weighted approaches. Why the choice of sampler matters. A wrong sampler does not merely degrade accuracy—it silently corrupts the decisions downstream. Three concrete scenarios illustrate the stakes and are based on our experiments. Welfare eligibility registry. A government agency profiles a 3M-row social registry daily to trigger data cleaning before updating an eligibility model. Using DAG-guided MCMC at a 5% budget on this administrative table (categorical columns dominating) yields a missing-value estimate that is systematically off by ≈20% relative error – large enough to miss a genuine spike in missing agency codes that would have triggered a data repair step. The same 5% budget with random uniform sampling achieves <1% relative error, reliably flagging or clearing the quality gate. IoT-driven predictive maintenance. A facility operator monitors 2.3M sensor readings per day from 54 devices to detect equipment faults (outlier rate ≈30%) before they propagate into a predictive maintenance model. DAG-guided MCMC concentrates draws on extreme-value rows, causing sample IQR to widen until virtually no row is flagged as an outlier—the estimated outlier rate collapses to
Data Quality Profiling at Scale with Progressive Sampling
3
≈ 3 × 10−6 (true: 29.6%). At every budget level, including 100%, the sampler reports near-zero defect rates while 30% of the dataset is corrupted. Random uniform avoids this collapse: at 5% budget it estimates 29.3%, within 0.3 points of ground truth. Urban AI retraining trigger. A city’s data team uses a 311 service-request dataset to retrain a predictive model weekly; the retraining trigger fires when the duplicate rate or missing rate shifts by more than 1 point from the reference profile. With a DAG-guided profiler (MRE 19.5% at 5% budget on NYC 311), the estimated profile fluctuates by several percentage points across runs even when the data is stable—generating false retraining triggers that consume GPU hours and delay production deployments. Random uniform at the same budget (MRE 0.49%) produces stable estimates that correctly reflect true distributional change. Progressive sampling as a practical alternative. Progressive sampling—evaluating quality indicators on a random or adaptively chosen subset of rows and extrapolating to the full table—offers a principled trade-off between computational cost and estimation accuracy. The notion of progressive (or incremental) sampling was formalized by Provost et al. [24], who showed that a geometric growth schedule dominates fixed-size sampling in practice; John and Langley [17] earlier demonstrated that dynamic sampling adapts better than static budgets for data mining tasks. The key question is which sampling strategy to use. Guided samplers, notably MCMC-based methods that exploit the attribute dependency graph (DAG) of the data, are a natural candidate: the attribute-dependency structure studied by Abedjan et al. [2,1] motivates focusing sampling effort on rows most likely to carry quality defects. Their appeal is intuitive: if quality errors cluster along known dependency edges, a structure-aware sampler should outperform blind random draws. Note that MCMC in this context is used for row sampling, distinct from its use for probabilistic inference in database systems [25]. The empirical question. Does guided MCMC sampling actually improve profiling accuracy in practice? We answer this question through a systematic benchmark spanning synthetic tabular data, three real-world administrative datasets (NYC 311 service requests, NYPD arrest records, UCI Adult census), and two IoT sensor datasets: a 2.3M-row real-world stream from the Intel Berkeley Research Lab [29] and a 510K-row synthetic dataset with matching schema. We compare nine progressive sampling strategies—random uniform, geometric, Yamane, cluster, Metropolis-Hastings, DAG-guided MCMC, stratified-column, stratified-quality, and importance-weighted. Each strategy is evaluated across five budgets (5%–50% of full-scan cost) and multiple quality indicators. Main finding. The answer is a clear negative: random uniform (RU) outperforms all guided MCMC methods on every real dataset we tested. The DAG-guided sampler is 11–49× worse than random uniform on NYC 311 and NYPD data (mean
4
L. Berti-Équille
relative error 0.195–0.263 vs. 0.004–0.020; Wilcoxon W = 0, p = 0.002, n = 9 independent pairs) and 13× worse on UCI Adult (0.263 vs. 0.020). At 5% sampling budget, random uniform achieves <1% profiling error on NYC 311, whereas DAG yields ≈20% error regardless of budget. At scale, DAG incurs super-linear cost (exponent 1.272 vs. 0.964 for random uniform) and is 12× slower at N = 5M rows while remaining 6× less accurate. We identify the root cause: the IQR-based error proxy used by guided samplers targets extreme numeric values, while quality defects in administrative and census data concentrate in categorical and string columns—a systematic proxy mismatch that importance-weighting corrections cannot fully overcome.
Contributions. We make the following contributions: C1 We formalize the progressive profiling loop (Algorithm 2), establishing geometric growth schedules and relative-change convergence criteria applicable to any sampling strategy. C2 We show that random_uniform (RU) achieves < 1% mean relative error at a 5% sampling budget on real-world administrative data (NYC 311, 500K rows, 9.4% missing), without requiring any schema metadata or dependency graph—meeting the accuracy threshold for production-grade DC-AI quality gates at one-twentieth of the full-scan cost. C3 We provide a rigorous comparative evaluation of nine sampling strategies, demonstrating that blind representative samplers (random uniform, cluster) outperform all proxy-guided methods on every real dataset; DAG is 11– 49× worse (W = 0, p = 0.002, n = 9 independent pairs over real-world datasets), establishing that the costly dependency-graph construction step can be eliminated from DC-AI profiling pipelines without accuracy loss. C4 We characterize scalability: RU scales near-linearly (O(N 0.964 )) with stable 5.5–6.3% error from N = 104 to N = 5 × 106 , while DAG degrades to superlinear cost (O(N 1.272 )). Confirmed on two XXL real datasets (with 7.4M and 6.0M rows), where DAG is 28–47× slower with 12–86× worse accuracy at 5% budget. C5 We show that random_uniform (RU) is the most robust baseline under injected errors across all error types and injection rates 1–30% (mean relative error 0.065, vs. 0.365 for DAG; 5.6× gap). C6 We provide directional evidence that attribute correlation modulates MCMC sampling quality: dag and gibbs both outperform metropolis_hastings across all correlation levels ρ ∈ {0.3, 0.5, 0.7, 0.9} (mean MRE 0.550/0.545 vs. 0.599, 8–9% reduction), though the effect is underpowered at n=5 seeds per stratum (minimum achievable Wilcoxon p = 0.03125). C7 We extend the benchmark to IoT sensor data, showing that RU achieves <1% MRE at 5% budget on 2.3M real sensor rows while DAG fails with 26.9% MRE at all budgets—a new failure mode we call IQR estimation collapse, distinct from the categorical proxy mismatch in administrative data.
Data Quality Profiling at Scale with Progressive Sampling
5
Section 1.1 formalizes the progressive profiling loop; Section 2 describes the nine sampling strategies; Section 3 reports experiments E1–E8; Section 4 analyzes failure modes; and Section 6 concludes. 1.1
Problem Statement
Consider a data engineer monitoring NYC 311 service requests (500K rows): what fraction of records have missing agency codes, which rows are duplicated, and how many contain implausible geographic values? The answers determine whether the dataset is fit for training a predictive model (the DC-AI quality gate from Section 1). Exhaustively computing these figures requires a full scan; our goal is to estimate them reliably from a small fraction of the data. The sampler’s choice is consequential: as the welfare-registry and IoT scenarios above illustrate, systematic estimation bias can propagate undetected through an entire DC-AI pipeline. Definitions 1–3 formalize the profile, the sampler, and the estimation error; Table 1 summarises all notation. Definition 1 (Data Quality Profile). Let D be a tabular dataset with N rows and M columns. The data quality profile Q(D) = (q1 , q2 , q3 , q4 ) is a 4dimensional vector whose components are: 1. missing_rate: fraction of (row, col) cell pairs whose value is null; 2. duplicate_rate: fraction of rows that are exact duplicates of at least one other row in D; 3. outlier _rate: fraction of rows containing at least one numeric value that lies beyond 1.5 IQR from Q1 or Q3 in its column (mild Tukey fence); 4. inconsistency_rate: fraction of rows that violate at least one functional dependency (FD) rule derived from the schema. These four indicators cover complementary defect types: completeness, uniqueness, distributional plausibility, and relational consistency, following established multidimensional models of information quality [6] and constituting a compact, interpretable summary for automated monitoring in DC-AI pipelines. Since computing Q(D) exactly requires a full scan of D—prohibitive for large datasets—we instead estimate it from a sample S ⊆ D of size n = ⌊b · N ⌋ at budget fraction b ∈ (0, 1]. Definition 2 (Progressive Sampler). A progressive sampler A takes a budget fraction b ∈ (0, 1] and returns a sample S ⊆ D of size ⌊b · N ⌋. The estimated profile Q̂(S) = (q̂1 , q̂2 , q̂3 , q̂4 ) approximates Q(D). Definition 3 (Relative Error). The mean relative error of an estimated profile Q̂(S) with respect to the ground truth Q(D) is: rel_err(b) =
4 |q̂i − qi | 1X min , 1.0 . 4 i=1 max(qi , 0.05)
6
L. Berti-Équille
The denominator is floored at 0.05 to avoid division by zero when a groundtruth indicator is near zero, and the ratio is capped at 1.0. The floor is set at 0.05 (5%) to match the practical significance threshold below which quality indicator changes are operationally negligible in the DC-AI monitoring contexts we target: a 0.1% missing rate and a 0.05% missing rate are both effectively zero for model-selection or data-release decisions. An indicator below 5% therefore contributes error bounded by the absolute deviation |q̂i − qi |, which we cap at 1.0 for robustness.
Table 1. Summary of notation used throughout the paper. Symbol
Meaning
D Tabular dataset N = |D| Number of rows M Number of columns b ∈ (0, 1] Sampling budget fraction n = ⌊bN ⌋ Sample size A Progressive sampler algorithm S Sample returned by A, S ⊆ D, |S| = n Q(D) Exact quality profile (ground truth) Q̂(S) Estimated quality profile from sample (q1 , . . . , q4 ) Missing, duplicate, outlier, inconsistency rates qi Per-row binary quality indicator σi Error-proxy score for row i wi Horvitz–Thompson importance weight b0 Initial budget fraction for progressive loop γ Sample-size growth factor (default 2) ε Relative-change convergence threshold k Patience: consecutive rounds below ε to stop ρ Pearson correlation (DAG edge if |ρcc′ | > .300) δ Convergence floor (Algorithm 2, default .050) B MCMC proposal batch size λ Metropolis temperature
2
Sampling Methods
2.1
Static Baselines
Random Uniform (RU). Draw n = ⌊bN ⌋ rows uniformly at random without replacement from D. Each row has equal selection probability n/N ; the quality estimate is an unweighted mean over the sample. Time complexity is O(N ) per budget level. RU requires no schema knowledge, no metadata, and no prior profiling.
Data Quality Profiling at Scale with Progressive Sampling
7
Geometric. Batch sizes decrease geometrically: the first batch draws ⌊N/2⌋ rows, the second ⌊N/4⌋, and so on, until the budget is exhausted. This mimics an anytime scheduler that front-loads large batches to obtain a rough estimate quickly, then refines with smaller ones. Like RU, Geometric requires no schema and operates in O(N ) per batch. For datasets with N ≥ 50,000 rows, the geometric sampler’s expected inter-row spacing N/n converges numerically to that of random uniform; pilot experiments confirmed identical MRE values to three decimal places across all tested conditions. We therefore exclude it from experiments on large-scale datasets (E6, XXL) and note that its results are subsumed by those of RU at the scales benchmarked here. Yamane. The Yamane formula [32] computes a one-shot sample size N , e = 0.05, nY = 1 + N e2
(1)
designed to bound the estimation error of a proportion at margin e. Yamane is a budget-oblivious baseline: its sample size is determined by the desired margin of error rather than the available fraction b. √ Cluster. We partition D into k = max(10, ⌊ N ⌋) consecutive blocks of approximately equal size (by storage order) and draw ⌈b · k⌉ blocks uniformly at random without replacement, retaining all rows in the selected blocks. Quality estimates are unweighted means over the retained rows. Cluster requires no schema knowledge, no proxy scores, and no pre-computation beyond a single pass to assign row indices to blocks; its sole hyperparameter k is set by the square-root rule for all experiments. Unlike stratified sampling, Cluster does not use any quality proxy: blocks are defined by row position alone, making Cluster as schema-free as random uniform sampling while allowing spatial locality in data quality to reduce estimation variance. 2.2
MCMC-Guided Samplers
The three guided samplers share a common error proxy that approximates perrow data quality without running the full profiler. For each numeric column c, the proxy score for row i is M
σi =
1 X 1[xic < Q1c − 1.5 IQRc M c=1 ∨ xic > Q3c + 1.5 IQRc ] +
M X
1 1[xic is missing], M c=1
(2)
i.e. the fraction of numeric columns in which row i is a Tukey outlier plus its missing-value fraction. Scores are computed once over the full dataset in O(N M ) before sampling begins.
8
L. Berti-Équille
Algorithm 1 DAG-Guided MCMC Sampler Require: Dataset D (N rows, M columns), budget b, batch size B, temperature λ, correlation threshold ρmin = 0.3 Ensure: Importance-weighted sample S ⊆ D, weights w 1: Compute per-row proxy scores σ ← ErrorProxy(D) 2: Build attribute DAG: add edge c → c′ if |ρcc′ | > ρmin 3: Precompute column priority p ← ClusterPriority(DAG) 4: Precompute column tail thresholds [lc , hc ] at 5th/95th percentiles 5: Warm-start: draw B rows ∝ σ; let S ← warm-start 6: σ̄curr ← mean(σ[S]) 7: while |S| < ⌊bN ⌋ do 8: Sample pivot column c∗ ∼ Categorical(p) 9: C ← {i ∈ / S : xic∗ ≤ lc∗ ∨ xic∗ ≥ hc∗ } 10: if C = ∅ then 11: C ←D\S 12: end if 13: Draw proposal batch P ⊆ C, |P | = min(B, |C|), uniformly 14: σ̄prop ← mean(σ[P ]) 15: if ln U < λ (σ̄prop − σ̄curr ), U ∼ Unif(0, 1) (natural logarithm) then 16: S ←S ∪P 17: else 18: S ← S ∪ UniformBatch(D \ S, B/4) 19: end if 20: Update σ̄curr incrementally 21: end while 22: w ← HTWeights(σ[S]) 23: return S, w
All three samplers correct for induced sampling bias via Horvitz–Thompson (HT) importance weighting (Section 2.3). Both the outlier quality indicator (Definition 1) and the sampling proxy use the mild Tukey fence (1.5×IQR)1 , ensuring the proxy targets the same anomaly type it is asked to estimate. Metropolis-Hastings (MH). At each MCMC step, a batch of B = 500 candidate rows is drawn uniformly. Acceptance follows the Metropolis criterion with temperature λ = 2.0. MH uses no dependency information; it steers proposals toward rows with higher error-proxy scores. DAG-guided (DAG). We design an IQR-proxy-weighted MCMC row-sampler guided by an attribute DAG inferred from column correlations, following the attribute-dependency perspective of Abedjan et al. [1]. An attribute dependency graph is built from the Pearson correlation matrix: a directed edge c → c′ is 1
A sensitivity analysis on D2 and D4 datasets shows that a stricter 3 × IQR fence would reverse the DAG–MH ordering on D4 dataset (MH gains substantially; DAG improves only marginally), while D2 rankings are unchanged; we use 1.5 × IQR as the default and note fence choice as a tunable design parameter.
Data Quality Profiling at Scale with Progressive Sampling
9
added whenever |ρcc′ | > 0.3. At each step, a pivot column is selected with probability proportional to its cluster-priority score; candidate rows are filtered to extreme tails of the pivot column. The acceptance criterion is identical to MH (λ = 2.0). Algorithm 1 gives the full procedure.2 Design note. Abedjan et al. [1] study column-level dependency analysis and data error detection; they do not propose a row-selection MCMC algorithm. Our DAG sampler is an original design that repurposes attribute-dependency structure for row-level progressive sampling: each row’s inclusion probability is proportional to its per-row IQR-outlier proxy score σi (Section 2.2), with the correlation DAG topology fixing the Metropolis–Hastings proposal distribution. This design bridges attribute-level dependency modeling and row-level progressive sampling and is, to our knowledge, novel in the data quality profiling literature. Gibbs. At each step, one numeric column c is chosen uniformly at random; a quantile band is selected and B rows are drawn from unsampled rows within that band. Gibbs always accepts (no rejection step). It provides a controlled ablation for studying the marginal value of cross-attribute dependencies (contribution C6, open finding). 2.3
Importance Weighting
Because MCMC samplers oversample high-proxy-score rows, we correct using Horvitz–Thompson (HT) weights [16]: wi =
1 , max(σi , ε0 )
ε0 = 10−6 ,
(3)
P normalised so that i wi = 1. We clip at the 95th percentile of {wi } before normalisation. The final quality estimate is the weighted mean of per-row indicators: P wi qi Q̂(S) = Pi∈S . (4) i∈S wi Static samplers (RU, Geometric, Yamane) use uniform weights (wi = 1/|S|). 2.4
Method Comparison
Table 2 summarises the ten candidate methods along three axes. Nine are fully benchmarked in experiments E1, E3–E6, and E8 (excluding Gibbs); geometric is additionally omitted from experiment E6 (XXL datasets) because it degenerates numerically to RU for N ≥ 50,000 (Section 2.1). Gibbs is described for theoretical completeness but excluded from these accuracy experiments: its O(N M ) initialization cost makes it impractical on the datasets used in this benchmark, and pilot runs confirmed runtimes 30–60× those of MH. It appears only in
10
L. Berti-Équille
Algorithm 2 ProgressiveProfiler Require: dataset D (N rows), sampler A, quality metrics Q, convergence threshold ε, initial fraction b0 , growth factor γ, patience k Ensure: quality profile P̂ , convergence round t∗ , final sample size n∗ 1: n ← ⌊b0 · N ⌋; t ← 0; stable ← 0 2: if A is guided (MH / Gibbs / DAG) then 3: Pre-compute σ ← ErrorProxy(D) 4: if A = DAG then 5: Build attribute DAG; precompute column priority p and percentile thresholds 6: end if 7: end if 8: S0 ← Draw(D, n, A, σ); P̂0 ← ComputeProfile(S0 , Q, w0 ) 9: while n < N and stable < k do 10: n ← min(⌊γ · n⌋, N ); t ← t + 1 11: St ← Draw(D, n, A, σ) 12: P̂t ← ComputeProfile(St , Q, wt ) |P̂t [q] − P̂t−1 [q]| 13: ∆ ← max q∈Q max(P̂ t−1 [q], δ) 14: if ∆ < ε then 15: stable ← stable + 1 16: else 17: stable ← 0 18: end if 19: end while 20: return P̂t , t∗ ← t, n∗ ← n
experiment E2, which provides directional—but underpowered (n = 5 seeds)— evidence on small synthetic data (contribution C6, open finding). In the benchmark experiments b0 = 0.05, γ = 2, ε = 0.01, and k = 1. 2.5
Progressive Profiling Loop
Algorithm 2 formalizes the progressive profiling loop underlying all experiments. The outer loop doubles the sample size at each round (growth factor γ = 2), motivated by Provost et al.’s efficiency result [24]. Convergence is declared when the maximum relative change across all quality indicators falls below threshold ε for k consecutive rounds.
3
Experiments
Experiment overview. Eight experiments test complementary facets of the benchmark. 2
This differs from MCMC in probabilistic databases [25], where chains are used for inference rather than row sampling.
Data Quality Profiling at Scale with Progressive Sampling
11
Table 2. Comparison of the ten progressive sampling strategies (N : dataset size; M : columns; B: batch size; “Schema?”: requires FD rules). Method
Information used
Random Uniform None (uniform) Geometric None (schedule) Yamane Desired margin e Cluster None (random blocks) Metropolis-H. Gibbs DAG Strat.-Col. Strat.-Quality Importance ∗
Per-step cost
Schema?
O(N ) O(N ) O(N ) one-shot O(N )
No No No No
IQR proxy scores O(N M ) init + O(B)/step No Column distribution O(N M ) init + O(B)/step No IQR proxy + DAG O(N M +E) init + O(B)/step No∗ Col. type + IQR proxy O(N M ) init + O(B)/draw No IQR proxy quantiles O(N M ) init + O(B)/draw No IQR proxy (weighted) O(N M ) init + O(B)/draw No
DAG builds the dependency graph from data correlations; no external schema required.
E1 compares all nine methods on primary datasets (D1, D2, D3, D4) across all budgets: cluster and RU achieve the lowest error (primary mean MRE 0.110–0.111); proxy-guided methods, including the four new stratified and importance-weighted variants, yield 0.20–0.35 (supporting contribution C3 with Table 5). E2 provides directional evidence that attribute correlation helps dag over MH on synthetic data, but is underpowered (contribution C6, open finding with Table 11). E3 shows dag is budget-invariant at 19–27% MRE on all real datasets regardless of b, while RU reaches 0.49% at 5% budget on D2 (contribution C2 with Table 8 ). E4 demonstrates RU is 5.6× more robust than dag under error injection (contribution C5 with Table 9). E5/6 establish scalability: RU scales near-linearly (O(N 0.964 )) while dag is 12–47× slower on data from 5M to 7.4M rows (contribution C4 with Table 10 and Table 12). E7 shows the consistent underperformance of proxy-guided methods with two controlled ablation experiments with Table 14; E8 reveals a new failure mode on IoT sensor data: IQR estimation collapse drives dag’s outlier estimate to ≈3×10−6 against a true rate of 29.6%, while RU achieves 0.23% MRE (contribution C7 with Table 13). 3.1
Experimental Setup
Datasets. We use D1, D2, D3, and D4 as primary datasets, D5 for scalability experiments, and D7-synth/D7-real for the IoT sensor benchmark (E8); see Table 3 for details. D4 (UCI Adult census income) extends coverage to a nonadministrative, non-NYC dataset, providing a domain-generalization check. D7real (Intel Berkeley Research Lab, 2004) consists of 2.3M readings from 54 temperature/humidity/light/voltage sensors deployed over four months; its quality
12
L. Berti-Équille
Table 3. Datasets. Missing% and Outlier% are ground-truth rates over the full dataset. † D4 outlier rate is zero-inflated; § D5 errors injected at 1–30% in E5. Name
Source
N
D1 NumPy synthetic tabular 100,000 D2 NYC 311 service requests 500,000 D3 NYPD Arrest Data 500,000 D4 UCI Adult census income 48,842 D5 Adult-derived synthetic 10K–5M D6-A Ultra-Marathon Running [18] 7,461,195 D6-B NYC Yellow Taxi Jan–Feb 2023 5,980,721 D7-synth IoT synthetic (IoTSensorGen.) 510,000 D7-real Intel Berkeley Lab sensors [29] 2,313,156
Cols Miss.% Out.% Role 8 9 18 14 15 13 19 11 11
5.0 9.4 .600 .900 var.§ 26.6 .600 5.4 .400
5.0 Primary (controlled) 3.4 Primary (real admin.) 15.9 Primary (real admin.) 36.1† Primary (non-NYC) var.§ Scalability only 10.5 XXL real .000 XXL real 16.0 IoT 29.6 IoT real
Table 4. Contribution#–claim–experiment–dataset correspondence. Each row maps a paper contribution (C1–C7, with C6 open finding) to the experiment that supports it and the datasets used. # Claim
Exp. Dataset(s)
C1 Formalizes progressive loop (Alg. 1 & 2) All All (design contribution) C2 RU <1% error at 5% budget E3 D2 (NYC 311, 500K) C3 RU/cluster outperform all proxy-guided by 11–49× E1 D1, D2, D3, D4 C4 RU near-linear; DAG super-linear E5/E6 D5 (synth., 10K–5M); D6-A (7.4M); D6-B (6.0M) C5 RU most robust under error injection E4 D1 (injected 1–30%) C6 DAG > MH on synth. corr. data (open) E2 D1, ρ ∈ {.300, .500, .700, .900} C7 RU <1% error on IoT; DAG IQR collapse E8 D7-synth (510K); D7-real (2.3M)
Data Quality Profiling at Scale with Progressive Sampling
13
profile is dominated by numeric sensor outliers (29.6% of rows) with negligible missing, duplicate, and FD inconsistency rates. Methods. We evaluate nine strategies: random_uniform (RU), geometric (excluded from E6 as it degenerates numerically to RU for N ≥ 50,000; see Section 2.1), yamane, cluster, dag, metropolis_hastings (MH), strat-col, strat-quality, and importance (Section 2). exhaustive (full scan) serves as the exact reference. Table 4 maps each claim to its supporting experiment and dataset. Platform and protocol. All experiments run in Python 3.12 with pandas and numpy on a single machine (Intel Core i9-9980HK CPU @ 2.40 GHz, 32 GB RAM; no GPU). Distributed-execution behaviour is outside scope. Each experiment uses 3 independent random seeds; E2 uses 5 seeds; E6 uses 10 seeds. Sampling budgets sweep b ∈ {0.05, 0.10, 0.20, 0.30, 0.50}. The primary accuracy metric is mean relative error (rel_err_mean) averaged over all four quality indicators. FD rules for the inconsistency indicator are mined automatically from each dataset [2]. Statistical comparisons use the Wilcoxon signed-rank test (one-sided). Experiments E3 and E5, which operate on larger datasets, used a batch size of B = 1,000 for performance; all other experiments used the default B = 500. 3.2
E1 — Accuracy Comparison
We compare all nine methods on D1, D2, D3, and D4 across all budgets and seeds (3 seeds × 5 budgets × 4 datasets = 60 observations per method pair). To avoid inflated effective sample size from positively correlated budget-level outcomes, we average MRE across budgets for each (dataset, seed) pair and apply a one-sided Wilcoxon signed-rank test on the resulting n = 9 independent pairs (3 seeds × 3 real datasets D2–D4). Table 5 reports mean relative error per method and dataset. Finding (C3). Among all nine methods, cluster and RU/geom. achieve the lowest primary mean MRE (0.110–0.111) across D1, D2, D3, and D4. On D2, dag=0.195 vs. RU=0.004 (≈49× worse); on D3, 0.213 vs. 0.019 (11×); on D4, 0.263 vs. 0.020 (13×). cluster matches RU closely: it excels on D3 (0.009, best) and D4 (0.017, best) while closely tracking RU on D2 (0.007 vs. 0.004). strat-q is competitive on D2 (0.004, tied best) and D3 (0.019) but degrades sharply on D4 (0.156), where quality proxies exhibit weaker stratification. strat-col and importance fail on all three real datasets (primary mean 0.313–0.351), comparable to dag and MH—they inherit the same IQR proxy mismatch since both concentrate sampling on high-IQR-proxy rows (Figure 1).3 Note on D1 MRE. RU’s elevated MRE on D1 (0.401) is a measurement artefact of the floor correction: the controlled synthetic data generation sets the 3
Five HT clip thresholds (none, 80th, 90th, 95th, 99th percentile) all yield identical DAG MRE (0.195±0.001) on D2 (15 conditions each), isolating DAG’s failure to the sampling step rather than the weighting step.
14
L. Berti-Équille
Table 5. E1 — Mean relative error by method and dataset (lower is better). All budgets and seeds pooled. Bold = lowest (or tied-lowest) MRE per column; D2 has a three-way tie (RU, geom., strat-q all at 0.004). Method
D1
D2
D3
D4 Prim. mean‡
RU geom. yamane
.401 .004 .019 .020 .401 .004 .019 .020 .465 .095 .055 .068
.111 .111 .170
dag MH
.524 .195 .213 .263 .526 .191 .210 .269
.299 .299
cluster .407 .007 .009 .017 strat-q .635 .004 .019 .156 strat-col .635 .421 .245 .102 importance .609 .238 .213 .190
.110 .204 .351 .313
Primary mean over D1+D2+D3+D4 (arithmetic). RU achieves lower budget-averaged MRE than DAG on all 9 pairs (D2–D4, 3 seeds × 3 datasets); one-sided Wilcoxon signed-rank test on n = 9 independent pairs: dag vs. RU, W = 0, p = 0.002. cluster=0.110 ≈ RU; strat-q=0.204 (D4 gap: 0.156 vs. 0.020). ‡
duplicate rate (GT = 0.025), outlier rate (GT = 0.025), and FD-inconsistency rate (GT = 0.015) below the 0.05 denominator floor, so even small absolute estimation errors yield large relative errors—with the outlier dimension alone hitting the cap of 1.0 (actual absolute error ≈ 0.060) and driving the aggregate. This floor-dominated regime is analysed in detail in Table 6. Table 6. Per-dimension MRE of RU/geom. on D1, averaged over all budgets and seeds. “Floor-dominated” = ground-truth rate < 0.05 (denominator is clamped to 0.05). The outlier dimension hits the MRE cap of 1.0 because the estimator detects statistical outliers (≈8.5% of rows) while the D1 generator injects only 2.5% labelled outliers—an absolute gap of ≈0.060 divided by the 0.05 floor gives MRE > 1. Quality Dimension
GT Rate RU Avg. MRE Floor-dominated?
Missing-value rate Duplicate rate Outlier rate FD-inconsistency rate
.050 .025 .025 .015
.027 .285 1.000 (cap) .294
No Yes Yes Yes
Aggregate MRE
—
.401
—
The missing-value rate (GT = 0.05, exactly at the floor) incurs only 2.7% MRE, confirming that RU estimates well-represented quality dimensions accurately. The aggregate MRE of 0.401 is therefore driven entirely by the three floor-dominated dimensions, not by any real failure of the sampler on D1.
Data Quality Profiling at Scale with Progressive Sampling
15
Table 7 provides a per-indicator breakdown confirming that dag’s error on D2 and D3 concentrates entirely in the outlier column (MRE = 0.682 and 0.846 respectively) rather than the missing, duplicate, or FD columns, identifying IQR threshold mismatch as the sole driver of failure. Table 7. Per-indicator mean MRE on D2 (NYC 311) and D3 (NYPD arrests), averaged across all budgets and seeds. Only Miss (missing) and Out (outlier) are shown; Dup and FD are identically zero across all methods in both datasets. Bold = lowest MRE per column. D2 (NYC 311) D3 (NYPD) Method
3.3
Miss
Out Miss
Out
RU .002 cluster .008 yamane .007 dag .099 MH .092 geom. .002 strat-col 1.000 strat-q .002 importance .271
.015 .000 .020 .000 .374 .003 .682 .007 .674 .007 .015 .000 .682 .023 .015 .000 .682 .007
.074 .035 .215 .846 .835 .074 .957 .074 .846
E3 — Budget–Accuracy Trade-off
Table 8 shows mean relative error of random_uniform and dag at each sampling budget on D2, D3, and D4. Table 8. E3 — Mean relative error vs. budget (3 seeds/cell). dag is budget-invariant at 19–27%. Bold = lowest RU error per dataset (D2 at 5%, C2; D3 and D4 at 50%). The bolded D2/RU value at b=5% is 0.0049 (0.49%, C2), shown rounded to .005. Dataset
Method b=5% b=10% b=20% b=30% b=50%
D2 (NYC 311)
RU dag
.005 .195
.007 .196
.004 .196
.003 .195
.003 .194
D3 (NYPD)
RU dag
.037 .213
.024 .213
.020 .213
.010 .213
.001 .213
D4 (Adult)
RU dag
.027 .273
.025 .274
.021 .260
.018 .262
.011 .264
Finding (C2). On D2 (NYC 311, 500K rows), random_uniform reaches 0.49% mean relative error at a 5% sampling budget, far below the 1%
16
L. Berti-Équille
threshold with only 25K rows inspected. strat-quality matches this on D2 (0.49% at b=5%); cluster reaches 1.42% at b=5% and converges to 0.21% at b=50% (Table 8 lists RU and dag; per-budget values for all nine methods are in the released results). dag is insensitive to budget on all three real datasets (19– 27% regardless of b), confirming that its proxy mismatch is structural (Figure 2).
D1 (Synthetic)
0.40
0.338 0.338
0.20
0.00 C MCM DAG-
Mean relative error
0.465
0.10
0.00 C MCM DAG-
0.055
MH Uniform ometric Yamane Ge
0.095
0.10
0.40
0.213 0.212
D4 (NYC 311)
0.20 0.195 0.193
0.00 C MCM DAG-
D5 (NYPD)
0.30 0.20
MH Uniform ometric Yamane Ge
Mean relative error
0.475 0.470
0.30
Mean relative error
Mean relative error
0.60
0.003 0.003
MH Uniform ometric Yamane Ge
D7 (Adult)
0.30 0.260 0.266 0.20 0.10
0.00 C MCM DAG-
0.068 0.011 0.011
MH Uniform ometric Yamane Ge
Fig. 1. E1 — Mean relative error per method at b=50% on all four primary datasets. D1=synthetic 100K; D2=NYC 311 (500K); D3=NYPD arrests (500K); D4=UCI Adult census (49K). DAG-MCMC is worst on all real-world datasets (D2–D4); Uniform and Cluster are near zero.
3.4
E4 — Robustness under Error Injection
We inject four error types (missing, duplicate, outlier, inconsistency) at rates 1%–30% into D1 and measure mean relative error (3 seeds per cell, b=0.50). Table 9 reports means aggregated over injection rates 1%–30%. Finding (C5). random_uniform (RU) maintains a mean error of 0.065 across all error types and injection rates (range: 0.04–0.13), while dag reaches 0.365 (range: 0.33–0.44), a 5.6× gap (Figure 3a).
Data Quality Profiling at Scale with Progressive Sampling
Mean relative error
D4 (NYC 311)
D5 (NYPD)
17
D7 (Adult)
0.25 0.20
DAG-MCMC Uniform Geometric MH Yamane
0.15 0.10 0.05 0.00
5%10%
20%
30%
50% 5%10%
Budget b (%)
20%
30%
50% 5%10%
Budget b (%)
20%
30%
50%
Budget b (%)
Fig. 2. E3 — Relative error vs. sampling budget b. D2=NYC 311; D3=NYPD arrests; D4=UCI Adult census. dag is budget-invariant at ≈19–27%; RU converges to sub-1% at b=5% on D2. Table 9. E4 — Mean relative error under error injection (rates 1–30%, 15 obs/cell). random_uniform (RU) is 5.6× more robust than dag. Error type
dag
RU
Missing .438 .051 Duplicate .342 .112 Outlier .349 .046 Inconsistency .332 .050 Mean
Missing
Mean relative error
0.6
.365 .065
Duplicate 0.3
0.4 0.2 0.0 0
10
20
Injection rate (%)
Outlier
0.4
0.4
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
30 0.0 0
10
20
Injection rate (%)
30 0.0 0
10
20
Injection rate (%)
30 0.0 0
DAG-MCMC Inconsistency
10
20
RU
Injection rate (%)
30
(a) Error vs. N
101 100 10 1 104
105
0.4 0.3
DAG-MCMC Uniform
0.2 0.1
5% threshold
0.0 104
106
Dataset size N
(b)
0.6
105
106
Dataset size N
Mean relative error
DAG-MCMC Uniform
Mean relative error
Wall-clock time (s)
Time vs. N Linear N
102
Error vs. =0.5
0.4 0.2 0.0 0.3
0.5
Correlation
DAG-MCMC MH Gibbs 0.7 0.9
(c)
Fig. 3. (a) E4 — Robustness: MRE vs. error injection rate (%, D1 synthetic, dag vs. RU, 3 seeds). (b) E5 — Scalability: wall-clock time (s) vs. N rows (D5 SDV synthetic, dag vs. RU, 1–3 seeds; see footnote). (c) E2 — Correlation ablation: MRE vs. Pearson ρ (D1 synthetic, dag vs. MH vs. Gibbs, 5 seeds per ρ). Lower MRE is better.
18
L. Berti-Équille
3.5
E5 — Scalability
We profile D5 at five scales N ∈ {10K, 100K, 500K, 1M, 5M}4 and fit a power law T = aN α on log-log axes. Table 10 reports wall-clock time and mean relative error. Table 10. E5 — Wall-clock time (s) and error vs. scale on D5 (b=0.50). Power-law exponents: RU α=0.964; dag α=1.272. Method
10K 100K 500K 1M
5M
Wall-clock time (seconds) dag .050 .390 2.59 8.29 169.0 RU .030 .100 .590 1.28 14.3 exhaustive .030 .150 .860 1.97 18.9 Mean relative error dag .424 .407 .355 .356 .355 RU .063 .058 .057 .057 .055 exhaustive .000 .000 .000 .000 .000
Finding (C4). random_uniform scales with a near-linear cost exponent (α=0.964) and achieves stable error around 5.5–6.3% across all five scales (Figure 3b). At N =5M, RU completes in 14.3 s—faster than exhaustive profiling (18.9 s) while incurring only 5.5% error. dag scales super-linearly (α=1.272): at N =5M it requires 169.0 s, 12× slower than RU and 6× less accurate. 3.6
E2 — Correlation Ablation
We assess whether attribute correlation strength modulates MCMC sampling quality on D1 by varying ρ ∈ {0.3, 0.5, 0.7, 0.9} (5 seeds per ρ, b=0.50). Table 11 reports mean relative error per method and ρ. Finding (C6) — open question. Both dag (0.550) and gibbs (0.545) are directionally better than MH (0.599) at all 20 seed-ρ pairs each (8–9% relative reduction), but per-ρ tests are underpowered: with n=5 seeds, the minimum achievable one-sided Wilcoxon p-value is 1/25 = 0.03125, which does not meet the Bonferroni-corrected threshold (α/4 = 0.0125). We treat this as inconclusive directional evidence requiring n ≥ 20 seeds (Figure 3c). 3.7
E6 — XXL Real-Dataset Scalability
We profile two XXL real datasets: D6-A (7,461,195 rows) and D6-B (5,980,721 rows). Ground truth is computed exhaustively once and cached; 10 seeds per condition. Table 12 reports mean relative error for both datasets. 4
The N =5M condition uses 1 seed due to wall-time constraints (≈170 s per dag run); the point is consistent with the trend at N =1M.
Data Quality Profiling at Scale with Progressive Sampling
19
Table 11. E2 — Mean relative error vs. correlation ρ on D1 (5 seeds, b=0.50). DAG shows a consistent directional advantage (lower MRE than MH at all ρ levels) but the effect does not meet the Bonferroni-corrected significance threshold (α/4 = 0.0125); the result is reported as open/inconclusive (C6). ρ
dag gibbs
MH p(dag<MH), n=5
.300 .500 .700 .900
.560 .540 .542 .556
.553 .601 .540 .594 .534 .602 .554 .598
Mean .550
.545 .599
.031 .031 p=0.03125 (= 1/25 ) is the minimum .031 .031 –
achievable one-sided Wilcoxon p-value with n=5. Direction is consistent: dag beats MH in all 20 seed-ρ pairs; gibbs beats MH in 21/25 pairs. Tests are underpowered per stratum.
Table 12. E6 — Mean relative error (%) on two XXL real datasets (10 seeds/cell), with mean wall-clock time (s) at each budget. dag is consistently high and far from RU regardless of budget or dataset. geometric omitted: at these budgets it degenerates to RU (identical values). Dataset
Method b=1% b=2% b=5% b=10% b=20%
D6-A (7.4M)
RU dag
1.27 .560 2.03 18.3 23.9 24.3
1.10 25.5
.710 25.4
D6-B (6.0M)
RU dag
.420 .350 .200 17.4 17.3 17.2
.110 17.4
.060 17.6
Wall-clock time (s, mean over 10 seeds) RU .240 .380 .800 D6-A (7.4M) dag 8.92 12.24 22.19 RU .160 .260 .610 D6-B (6.0M) dag 14.57 17.90 27.58
1.46 40.63 1.24 42.96
2.72 79.38 2.10 74.77
20
L. Berti-Équille
Finding (C4 — XXL extension). On both XXL datasets, random_uniform achieves well under 5% mean relative error at 5% budget (2.03% on D6-A; 0.20% on D6-B). At 5% budget, RU completes in 0.80 s (D6-A) and 0.60 s (D6-B) while dag requires 22.19 s and 28.13 s respectively, yielding timing gaps of 28× (D6-A) and 47× (D6-B)—both larger than the 12× at N = 5M synthetic, confirming super-linear DAG scaling on real data. 3.8
E8 — IoT Sensor Benchmark
We profile two IoT datasets: D7-synth (510K synthetic rows, injected defects: 5.4% missing, 2.0% duplicates, 16.0% outliers, 2.9% FD inconsistencies) and D7-real (2.3M rows from the Intel Berkeley Research Lab [29]; ground truth computed exhaustively: 0.4% missing, 0.0% duplicates, 29.6% outliers, 0.0% FD inconsistencies). Outliers arise from genuine sensor malfunctions (temperature spikes, voltage drops)—a numeric-dominant quality profile absent in all prior datasets. Table 13 reports mean relative error (MRE, %) at 5% and 50% budgets over 3 seeds. Table 13. E8 — Mean relative error (%) on IoT datasets, 3 seeds/cell. Bold = lowest MRE per row. cluster matches RU/geom. on D7-synth; strat-q matches RU on D7-real (uniform outlier distribution). dag, MH, strat-col, importance fail on D7-real via IQR estimation collapse (see Section 4). Method
D7-synth (510K) D7-real (2.3M) b=5%
b=50% b=5% b=50%
RU geom. yamane cluster
23.5 23.5 28.5 23.5
12.2 .230 12.2 .230 28.5 1.33 11.9 2.36
.180 .180 1.33 .470
dag MH strat-q strat-col importance
72.6 71.9 53.0 53.0 48.5
59.7 26.9 57.6 26.8 45.0 .230 45.0 22.8 35.7 19.0
26.9 26.9 .180 22.8 26.9
Finding (C7 — IoT sensor benchmark). On D7-real, random_uniform, geom., and strat-q all achieve 0.23% MRE at 5% budget—below the 1% threshold of C2 on a dataset 4.6× larger than NYC 311 (14.3× speedup for RU). cluster starts at 2.36% MRE at 5% budget but converges to 0.47% at 50%. dag reports 26.9% MRE across all budgets including 100%, while running 11× slower than exhaustive; strat-col (22.8%) and importance (19.0%) fail via the same IQR estimation collapse. On D7-synth, RU, geometric, and cluster (all ≈12–23% at 5–50%) outperform DAG (59.7%), MH (57.6%), and the IQRproxy-stratified methods (strat-q: 45–53%) by a factor of 2–4. With n=3 seeds,
Data Quality Profiling at Scale with Progressive Sampling
21
the minimum achievable one-sided Wilcoxon p-value is 1/23 = 0.125; E8 results are therefore reported descriptively rather than with formal significance, consistent with the per-stratum treatment in E2. The point estimates (26.9% vs. 0.23% MRE, a ratio of ≈117×) are large enough to be practically unambiguous, but formal statistical confirmation requires n ≥ 7 seeds. The DAG failure on D7-real is mechanistically different from the categorical proxy mismatch on administrative data (Section 4): it is an estimation collapse. DAG’s non-uniform sample over-represents rows near IQR boundaries; in the resulting sample, the empirical Q1/Q3 shift outward, widening the sample-level IQR so that almost no sampled row is flagged as an outlier. The estimated outlier rate collapses to ≈ 3 × 10−6 against a true rate of 29.6%, contributing a per-indicator relative error of ≈ 1.0 that dominates the MRE. Random uniform sampling, in contrast, draws a representative cross-section whose empirical IQR matches the population, yielding an estimated outlier rate of 29.3% (true: 29.6%) at every tested budget. Practical recommendation for DC-AI pipelines. For IoT or sensor streaming data where quality defects are predominantly numeric and uniformly distributed across devices, random uniform sampling at a 5–10% budget is the strongly preferred choice. Markov chain methods add substantial overhead (11–13× slower) without accuracy benefit; their advantage—if any—requires data where defects are spatially concentrated and structurally encoded, conditions not met in real sensor deployments.
4
Discussion
Why does guided sampling fail on real data? Five failure modes explain the consistent underperformance of proxy-guided methods; two controlled ablation experiments (E7 a and b) confirm the attribution. IQR proxy mismatch. The IQR-based error proxy detects numeric outliers— extreme latitude/longitude values in NYC 311 (D2/D3) or capital_gain/loss spikes in UCI Adult (D4). Quality defects in all three real datasets, however, concentrate in categorical and string-typed columns. This mismatch is structural: any IQR-style proxy is blind to categorical data quality by construction [14]. Horvitz-Thompson weighting instability. When row scores cluster near zero (string-heavy datasets), importance weights wi ∝ 1/scorei diverge toward 106 . Even after clipping, over-weighted rows dominate the estimate and bias all indicators toward zero. Proxy ablation (E7a). A controlled ablation (dag_uniform) retains DAG’s graph proposal but replaces IQR-based HT weights with uniform weights. On D2 at b=50%, dag_uniform achieves 3.8% MRE vs. DAG’s persistent 19.5%—confirming the IQR proxy introduces a structural bias. We note one non-monotonic exception: at b = 5% on D2, dag_uniform achieves 30.5% MRE—worse than full dag (19.6%)—indicating that at very low budget, the IQR weights partially compensate for the proposal bias introduced by the DAG structure. The dominance of
22
L. Berti-Équille
the weighting mechanism over the proposal bias is therefore budget-dependent: it is negligible at b ≤ 5% and pronounced at b ≥ 10% (daguniform = 3.8% vs. dag = 19.5% at b = 50%). This motivates a refined root-cause framing: the IQR weighting step is the dominant failure source at operational budgets (b ≥ 10%); at very low budget, the DAG proposal and weighting interact and partially cancel. Table 14 reports the full ablation. Hyperparameter robustness (E7b). A sweep over MCMC batch size B ∈ {100, 200, 500, 1000} on D2 confirms that DAG’s MRE varies by less than 0.001 across all four values (19.48–19.57%); the reported B=500 default is not a cherrypicked optimum. Wall-clock time decreases with larger B (2.56 s at B=100 to 0.90 s at B=1000) but accuracy is flat—the proxy mismatch dominates regardless of step granularity (detailed results available in released code).
Table 14. E7a — Proxy ablation: dag_uniform retains DAG’s graph proposal but replaces IQR-based HT weights with uniform weights. Columns: dag = full DAG-guided MCMC (IQR proxy + graph); dag_unif. = graph proposal only (uniform weights); RU = random uniform. Means over 3 seeds. Bold = lowest MRE per row. Dataset
b (%) dag dag_unif. RU
D2 (NYC 311) 5 D2 (NYC 311) 50 D3 (NYPD) 5 D3 (NYPD) 50
.196 .195 .213 .213
.305 .005 .038 .003 .024 .037 .009 .001
IQR estimation collapse (IoT data). On D7-real (29.6% true outlier rate), the failure mechanism is distinct from categorical proxy mismatch. DAG’s nonuniform sample concentrates extreme-value rows, shifting the sample’s Q1/Q3 outward and widening the IQR so that virtually no sampled row is classified as an outlier. The estimated outlier rate collapses to ≈ 3 × 10−6 , yielding ≈ 1.0 per-indicator relative error that persists even at 100% budget— confirming this is an estimator bias, not a sampling coverage issue. Proxy-guided non-representativeness generalises beyond MCMC. The new stratified and importance methods confirm that the root cause is not MCMCspecific: any sampler that concentrates draws on high-IQR-proxy rows shifts the sample IQR outward and biases all downstream estimates. strat-col (Neyman allocation by column type + IQR proxy) and importance (weighted reservoir sampling ∝ proxy score) both achieve primary mean MRE 0.31–0.35— comparable to dag/MH—because they amplify the same proxy mismatch. By contrast, cluster (random consecutive blocks, no proxy) matches RU (primary mean 0.110 vs. 0.111), establishing that representativeness, not domain knowledge, is the decisive property for multi-indicator quality profiling. Super-linear computational cost. At each batch step, DAG resamples the entire candidate pool, making total cost super-linear in N (O(N 1.272 ) empirically). At N = 5M rows this is 169 s against RU’s 14.3 s (12× slowdown with 6× worse
Data Quality Profiling at Scale with Progressive Sampling
23
accuracy). On XXL real data the gap widens further: 28× on D6-A and 47× on D6-B. Implications for DC-AI practitioners. Data quality profiling occupies three positions in a DC-AI pipeline: ingestion-time (profile each arriving batch), pretraining (verify the full training set before a model fit), and drift monitoring (compare the current profile against a stored reference baseline). Our results point to the same configuration in all three settings: use random_uniform or cluster at a 5–10% budget. At ingestion-time, a 5% budget over a 500K-row daily update scans only 25K rows, achieving <1% MRE on all four quality indicators with latency negligible against typical ingestion windows. At pre-training, the same budget over a 5M-row training corpus requires scanning 250K rows, completing in under 15 seconds on commodity hardware (vs. 169 seconds for a full scan; E5)—freeing the remainder of the training budget for model iteration rather than data scanning. For drift monitoring, the profile estimate is precise enough (<1% MRE on real data) to detect meaningful shifts in missing-value rates, duplicate fractions, and outlier densities between pipeline runs. Crucially, neither random_uniform nor cluster requires any schema metadata, dependency graph, or domain-specific tuning. This schema-free property is essential in DC-AI systems where data sources are heterogeneous and schemas evolve: the same profiler applies without reconfiguration to administrative tables, IoT sensor streams, and census microdata. DAG-guided methods, by contrast, require constructing an attribute correlation graph—a non-trivial data engineering effort that must be repeated when the schema changes, and which our results demonstrate adds no accuracy benefit on any real dataset tested. Under error injection RU is also the most robust choice (<13% MRE at injection rates up to 30%; E4), making it the safe default under both clean and corrupted conditions. The data-type-specific lesson is as follows: on administrative data with categorical defects the IQR proxy is structurally mismatched; on numeric IoT data with high outlier rates the IQR estimator collapses; in both cases any proxyguided method adds overhead without benefit. The decisive property for multiindicator quality profiling is representativeness—drawing a sample whose empirical distribution mirrors the population—not domain knowledge encoded in a proxy or graph. Whether genuinely structured relational or knowledge-graph data changes this conclusion remains an open question (E2). Limitations. Real-world data evaluation covers administrative, census, and IoT sensor tabular data; time-series (beyond single-stream IoT), knowledge-graph, multi-relational and multimodal settings are out of scope. All experiments use 3– 10 seeds [8]. Our open finding (C6) would require n ≥ 20 seeds for confirmation.
5
Related Work
Data profiling and quality assessment. Data profiling encompasses automated discovery of metadata, structural properties, and quality indicators from datasets.
24
L. Berti-Équille
Abedjan et al. provide a comprehensive taxonomy and benchmark of profiling systems [2,1]. Schelter et al. present an automated large-scale data quality verification system integrating declarative constraint checking into ML pipelines [27]. Grafberger et al. extend this to runtime distribution debugging across pipeline stages, monitoring data slices between training and serving [12]; our work targets the complementary pre-deployment question of how accurately quality profiles can be estimated from a small fraction of the data. Naumann and Herschel lay the theoretical foundations of data quality dimensions [20]. Closely related to our relational-consistency indicator, Berti-Équille et al. [7] study the discovery of genuine functional dependencies from relational data with missing values, a prerequisite for the FD-violation defects our profile measures. On the repair side, Rekatsinas et al. [26] perform holistic data repair with probabilistic inference. Whang et al. survey data collection and quality challenges in ML pipelines from a DC-AI perspective, identifying heterogeneous quality failures across column types as primary obstacles to reliable model training [31]—the same column-type heterogeneity that explains the IQR proxy mismatch we identify in Section 4. Berti-Equille examines the interaction between data quality and downstream analytical costs [4]—the same cost–quality trade-off motivating our progressive profiling approach. A critical limitation shared by all these systems is that they operate exhaustively: the full dataset must be processed before any quality indicator is reported. Our work addresses this gap by studying how well quality profiles can be estimated from progressively drawn samples. Progressive and approximate query processing. The approximate query processing (AQP) literature addresses the cost of exact query evaluation. Hellerstein et al. pioneer online aggregation [15]; Haas and Hellerstein extend this to joins [13]. BlinkDB [3] and Verdict [22] build pre-computed stratified samples for ad-hoc analytical queries. Most recently, Zhu proposes B-AQP, which uses block-level (cluster) sampling for AQP and achieves a 41% error reduction over uniform sampling on aggregate queries [34]; their finding that block draws are competitive with uniform sampling on aggregate estimation aligns with our result that our cluster sampler matches random uniform on multi-indicator quality profiling. However, AQP systems target aggregate queries over a single statistic; data quality profiling involves simultaneously estimating multiple heterogeneous indicators, leaving open the question of which sampling strategy best suits this multi-indicator setting—a question we answer empirically. Sampling for data quality. Cormode et al. survey synopses for massive datasets [10]. Vitter’s reservoir sampling [30] and weighted extensions of Efraimidis and Spirakis [11] provide the algorithmic foundation for importanceweighted sampling underlying our MCMC-guided methods; our experiments ask whether these importance weights actually help for multi-indicator profiling, and find they do not on real administrative data. Stratified and adaptive sampling. Stratified random sampling [21] allocates sample sizes to strata proportionally to their variance. Adaptive sampling [28] dy-
Data Quality Profiling at Scale with Progressive Sampling
25
namically adjusts stratum boundaries. We benchmark two stratified variants: strat-col partitions rows by column type and IQR proxy, and strat-quality partitions by IQR proxy quantiles, both using Neyman allocation. Contrary to expectation, both inherit the IQR proxy mismatch and match or exceed dag/MH error on real data; only strat-quality reaches RU-level accuracy on D2 and D7-real where quality defects happen to correlate with the proxy. Foundational progressive sampling. Provost et al. [24] established that geometric growth schedules are efficient for learning curves. John and Langley [17] showed that dynamic sampling outperforms static budgets. The present work applies the same principle to quality profiling metrics and evaluates it across nine strategies on real administrative and IoT data at scale. MCMC row-sampling for data quality profiling. MCMC methods for row-level selection in data quality profiling are largely unexplored in the literature. Existing work, including the comprehensive survey and benchmark of Abedjan et al. [1], focuses on column-level dependency analysis and automated error detection, not on row-level sampling strategies for profiling estimation. Our DAG-guided sampler is therefore an original contribution that bridges attribute-level dependency modeling—inspired by the column-correlation perspective of Abedjan et al.—and row-level progressive sampling: it uses the attribute DAG to shape a Metropolis–Hastings proposal distribution over rows, weighted by an IQR-based error proxy. Empirically, this bridge does not improve profiling accuracy over blind sampling on real tabular data, a finding that holds across administrative, census, and IoT data types and constitutes a reproducible negative result for structure-aware row samplers. Our contribution in context. To our knowledge, no prior work systematically compares progressive sampling strategies for multi-indicator data quality profiling at scale. The data-centric AI movement [19,33,23], part of a broader round trip between machine learning and data management [5], has renewed interest in profiling pipelines and raised the expectation that structure-aware, dependencyguided samplers should outperform blind draws. Our work overturns this assumption: the IQR-based proxy that DAG-guided methods rely on is blind to categorical quality defects, making random uniform sampling faster and more accurate on all real datasets tested—a reproducible negative result with direct implications for production DC-AI data monitoring pipelines.
6
Conclusion
Data-centric AI places data quality at the centre of the ML lifecycle, yet the question of how to measure that quality efficiently at scale has received little systematic attention. We have shown that representativeness, not domain knowledge or quality proxies, is the decisive property for multi-indicator data quality profiling. Across six real datasets—three administrative (NYC 311 and
26
L. Berti-Équille
NYPD arrests, 500K rows each; UCI Adult census, 49K rows), two XXL tabular (D6-A: 7.4M rows, D6-B: 6.0M rows), and one IoT sensor stream (D7-real: 2.3M rows)—plus synthetic tabular data scaled to 5M rows, blind representative samplers (random uniform, cluster) dominate all nine benchmarked strategies on accuracy, cost, and robustness. DAG-guided MCMC is 11–49× less accurate on real datasets and 12× slower at N = 5M; stratified and importance-weighted methods that rely on IQR-based proxies inherit the same structural failure (stratcol and importance: MRE 0.31–0.35; strat-quality intermediate at 0.20). Cluster sampling—which draws random consecutive blocks without any proxy—matches random uniform (primary mean MRE 0.110 vs. 0.111) with O(N ) cost and no tuning. Practical recommendation for DC-AI pipelines. Use random_uniform or cluster at a 5–10% sampling budget for routine data quality monitoring. random_uniform is also the most robust baseline under error injection across all four error types (mean error 0.065 vs. 0.365 for DAG) at injection rates up to 30% (E4), making it the default choice under both normal and error-prone conditions. DC-AI design principle. This benchmark instantiates a broader datacentric lesson: when a hand-crafted proxy (IQR score) guides a sampler (MCMC chain), the proxy’s coverage determines the system’s utility. In tabular DCAI settings—where quality defects span numeric, categorical, and relational dimensions—no single numeric proxy captures the full quality surface. The practical consequence is that the schema-free inductive bias of random uniform sampling (every row is equally informative a priori) is better matched to the actual structure of data quality defects than any proxy-guided alternative. Profiling infrastructure for DC-AI pipelines should therefore be evaluated not on theoretical elegance but on empirical accuracy across the data types it will encounter—the approach this benchmark instantiates. Reproducibility. Our benchmark—covering six real datasets (up to 7.4M rows) and synthetic data scaled to 5 × 106 rows, nine sampling strategies, and four error types—is fully reproducible; code, data, and scripts are available at https://github.com/LaureBerti/progressive-profiling and permanently archived on Zenodo (DOI: 10.5281/zenodo.21628028). Future work. One concrete direction remains: resolving whether DAGguided sampling helps on genuinely structured relational or knowledge-graph data requires replacing the random stub with a real dataset and running E2 at n ≥ 20 seeds per ρ level [9]. Stratified sampling with a proxy that captures categorical quality defects (not IQR-based) remains an open avenue. Acknowledgments. This work was carried out at IRD, ESPACE-DEV, Montpellier, France. Disclosure of Interests. The author has no competing interests to declare that are relevant to the content of this article.
Data Quality Profiling at Scale with Progressive Sampling
27
References 1. Abedjan, Z., Chu, X., Deng, D., Fernandez, R.C., Ilyas, I.F., Ouzzani, M., Papotti, P., Stonebraker, M., Tang, N.: Detecting data errors: Where are we and what needs to be done? In: VLDB. vol. 9, pp. 993–1004 (2016). https://doi.org/10.14778/ 2994509.2994518 2. Abedjan, Z., Golab, L., Naumann, F.: Profiling relational data: A survey. VLDB Journal 24(4), 557–581 (2015). https://doi.org/10.1007/s00778-015-0389-y 3. Agarwal, S., Mozafari, B., Panda, A., Milner, H., Madden, S., Stoica, I.: BlinkDB: Queries with bounded errors and bounded response times on very large data. In: EuroSys. pp. 29–42 (2013). https://doi.org/10.1145/2465351.2465355 4. Berti-Équille, L.: Data quality awareness: A case study for cost optimal association rule mining. Knowledge and Information Systems 11(2), 191–215 (2007). https: //doi.org/10.1007/s10115-006-0006-x 5. Berti-Équille, L., Bonifati, A., Milo, T.: Machine learning to data management: A round trip. In: 34th IEEE International Conference on Data Engineering (ICDE). pp. 1735–1738 (2018). https://doi.org/10.1109/ICDE.2018.00226 6. Berti-Équille, L., Comyn-Wattiau, I., Cosquer, M., Kedad, Z., Nugier, S., Peralta, V., Cherfi, S.S.S., Thion-Goasdoué, V.: Assessment and analysis of information quality: A multidimensional model and case studies. International Journal of Information Quality 2(4), 300–323 (2011). https://doi.org/10.1504/IJIQ.2011. 043780 7. Berti-Équille, L., Harmouch, H., Naumann, F., Novelli, N., Thirumuruganathan, S.: Discovery of genuine functional dependencies from relational data with missing values. Proceedings of the VLDB Endowment (PVLDB) 11(8), 880–892 (2018). https://doi.org/10.14778/3204028.3204032 8. Bouthillier, X., Delaunay, P., Bronzi, M., Trofimov, A., Nichyporuk, B., Szeto, J., Sepah, N., Raff, E., Madan, K., Voleti, V., Kahou, S.E., Michalski, V., Serdyuk, D., Arbel, T., Pal, C., Varoquaux, G., Vincent, P.: Accounting for variance in machine learning benchmarks. In: MLSys (2021). https://doi.org/10.48550/arXiv. 2103.03098 9. Button, K.S., Ioannidis, J.P.A., Mokrysz, C., Nosek, B.A., Flint, J., Robinson, E.S.J., Munafò, M.R.: Power failure: why small sample size undermines the reliability of neuroscience. Nature Reviews Neuroscience 14(5), 365–376 (2013). https://doi.org/10.1038/nrn3475 10. Cormode, G., Garofalakis, M., Haas, P.J., Jermaine, C.: Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases 4(1–3), 1–294 (2011). https://doi.org/10.1561/1900000004 11. Efraimidis, P.S., Spirakis, P.G.: Weighted random sampling with a reservoir. In: Information Processing Letters. vol. 97, pp. 181–185 (2006). https://doi.org/10. 1016/j.ipl.2005.11.003 12. Grafberger, S., Groth, P., Stoyanovich, J., Schelter, S.: Data distribution debugging in machine learning pipelines. VLDB Journal 31, 1103–1126 (2022). https://doi. org/10.1007/s00778-021-00726-w 13. Haas, P.J., Hellerstein, J.M.: Ripple joins for online aggregation. In: SIGMOD. pp. 287–298 (1999). https://doi.org/10.1145/304181.304208 14. Hellerstein, J.M.: Quantitative data cleaning for large databases. Tech. rep., United Nations Economic Commission for Europe (UNECE) (2008), http://db. cs.berkeley.edu/jmh/papers/cleaning-unece.pdf
28
L. Berti-Équille
15. Hellerstein, J.M., Haas, P.J., Wang, H.J.: Online aggregation. In: SIGMOD. pp. 171–182 (1997). https://doi.org/10.1145/253262.253291 16. Horvitz, D.G., Thompson, D.J.: A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association 47(260), 663–685 (1952). https://doi.org/10.1080/01621459.1952.10483446 17. John, G.H., Langley, P.: Static versus dynamic sampling for data mining. In: KDD. pp. 367–370 (1996), https://cdn.aaai.org/KDD/1996/KDD96-069.pdf 18. Kaggle: The big dataset of ultra-marathon running. https://www.kaggle. com/datasets/aiaiaidavid/the-big-dataset-of-ultra-marathon-running/ data (2021), https://www.kaggle.com/datasets/aiaiaidavid/ the-big-dataset-of-ultra-marathon-running/data, accessed: May 2026 19. Mazumder, M., Banbury, C., Yao, X., Karlaš, B., Rojas, W.G., Diamos, S., Diamos, G., He, L., Parrish, A., Kirk, H.R., et al.: Dataperf: Benchmarks for datacentric AI development. In: Advances in Neural Information Processing Systems 36 (NeurIPS), Datasets and Benchmarks Track (2023). https://doi.org/10.48550/ arXiv.2207.10062 20. Naumann, F., Herschel, M.: An Introduction to Duplicate Detection. Morgan & Claypool Publishers (2010). https://doi.org/10.1007/978-3-031-01835-0 21. Neyman, J.: On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society 97(4), 558–625 (1934). https://doi.org/10.2307/2342192 22. Park, Y., Mozafari, B., Sorenson, J., Wang, J.: VerdictDB: Universalizing approximate query processing. In: SIGMOD. pp. 1461–1476 (2018). https://doi.org/ 10.1145/3183713.3196905 23. Patel, H., Guttula, S., Mittal, R.S., Manwani, N., Berti-Équille, L., Manatkar, A.: Advances in exploratory data analysis, visualisation and quality for data centric AI systems. In: KDD. pp. 4814–4815 (2022). https://doi.org/10.1145/3534678. 3542604 24. Provost, F., Jensen, D., Oates, T.: Efficient progressive sampling. In: KDD. pp. 23–32 (1999). https://doi.org/10.1145/312129.312188 25. Ré, C., Suciu, D.: Approximate lineage for probabilistic databases. PVLDB 1(1), 797–808 (2008). https://doi.org/10.14778/1453856.1453943 26. Rekatsinas, T., Chu, X., Ilyas, I.F., Ré, C.: HoloClean: Holistic data repairs with probabilistic inference. In: VLDB. vol. 10, pp. 1190–1201 (2017). https://doi. org/10.14778/3137628.3137631 27. Schelter, S., Lange, D., Schmidt, P., Celikel, M., Biessmann, F., Grafberger, A.: Automating large-scale data quality verification. Proceedings of the VLDB Endowment (PVLDB) 11(12), 1781–1794 (2018). https://doi.org/10.14778/3229863. 3229867 28. Thompson, S.K.: Adaptive cluster sampling. Journal of the American Statistical Association 85(412), 1050–1059 (1990). https://doi.org/10.1080/01621459. 1990.10474975 29. Tolle, G., Polastre, J., Szewczyk, R., Culler, D., Turner, N., Tu, K., Burgess, S., Dawson, T., Buonadonna, P., Gay, D., Hong, W.: A macroscope in the redwoods. In: Proc. 3rd ACM Conference on Embedded Networked Sensor Systems (SenSys) (2005). https://doi.org/10.1145/1098918.1098925, Intel Berkeley Research Lab dataset: http://db.csail.mit.edu/labdata/ 30. Vitter, J.S.: Random sampling with a reservoir. ACM Transactions on Mathematical Software 11(1), 37–57 (1985). https://doi.org/10.1145/3147.3165
Data Quality Profiling at Scale with Progressive Sampling
29
31. Whang, S.E., Roh, Y., Song, H., Lee, J.G.: Data collection and quality challenges in deep learning: A data-centric AI perspective. VLDB Journal 32(4), 791–813 (2023). https://doi.org/10.1007/s00778-022-00775-9 32. Yamane, T.: Statistics: An Introductory Analysis. Harper and Row, New York, 2nd edn. (1967), https://openlibrary.org/isbn/9780060473136 33. Zha, D., Bhat, Z.P., Lai, K.H., Yang, F., Jiang, Z., Zhong, S., Hu, X.: Datacentric artificial intelligence: A survey. ACM Computing Surveys 57(5) (2025). https://doi.org/10.1145/3711118 34. Zhu, Y.: Efficient approximate query processing with block sampling. In: Conference on Innovative Data Systems Research (CIDR) (2025), https://www.vldb. org/cidrdb/papers/2025/p3-zhu.pdf