Paper deep dive
Data Quality Profiling at Scale with Progressive Sampling: A Benchmark for Data-Centric AI Pipelines
Laure Berti-Equille
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/1/2026, 11:40:20 AM
Summary
This paper benchmarks nine progressive sampling strategies for data quality profiling in data-centric AI pipelines. It demonstrates that blind representative samplers, specifically random uniform and cluster sampling, significantly outperform proxy-guided methods like DAG-guided MCMC in terms of accuracy and scalability. The study identifies a root cause for the failure of guided samplers: an IQR proxy mismatch where proxy-guided methods over-pursue numeric outliers while quality defects often concentrate in categorical columns. The findings suggest that schema-free random uniform sampling is sufficient and optimal for production-grade quality profiling at scale.
Entities (9)
Relation Signals (6)
Random Uniform → outperforms → DAG-Guided MCMC
confidence 98% · DAG is 11-49x worse... random uniform achieves 0.49% mean relative error... DAG-guided MCMC yields 19.5%
Data Quality Profiling → isfoundationalfor → Data-Centric AI Pipelines
confidence 96% · Data quality profiling... is foundational for data-centric AI pipelines
Random Uniform → matchesaccuracyof → Cluster Sampling
confidence 95% · Cluster sampling matches random uniform (MRE 0.110 vs. 0.111)
DAG-Guided MCMC → hascomplexity → Super-linear
confidence 94% · DAG is super-linear (O(N^{1.272}))
Random Uniform → hascomplexity → Near-linear
confidence 94% · random uniform is near-linear (O(N^{0.964}))
DAG-Guided MCMC → suffersfrom → IQR Proxy Mismatch
confidence 93% · The root cause is an IQR proxy mismatch: proxy-guided samplers over-pursue numeric outliers
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 alternative; the open question is which strategy best preserves profile fidelity at scale. We benchmark nine 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 Ultra-Marathon Running (up to 7.4M rows), and synthetic data scaled to 5x10^6 rows. Contrary to the assumption sharpens 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% (approx. 40x worse), and across all real datasets DAG is 11-49x worse (Wilcoxon W=0, p=0.002, n=9 pairs). Cluster sampling matches random uniform (MRE 0.110 vs. 0.111); proxy-guided methods share DAG's failure mode (MRE 0.20-0.35). At scale, random uniform is near-linear (O(N^{0.964})) while DAG is super-linear (O(N^{1.272})), running 28--47x slower on ultra-large data with 6x worse accuracy. The root cause is 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: representativeness, not domain knowledge, determines sampler quality -- schema-free random uniform or cluster sampling suffices for production-grade quality profiling at scale.
Tags
Links
- Source: https://arxiv.org/abs/2607.25356v1
- Canonical: https://arxiv.org/abs/2607.25356v1
Trouble viewing inline? Open PDF directly →
Full Text
72,103 characters extracted from source content.
Expand or collapse full text
11institutetext: IRD, ESPACE-DEV, 500, rue Jean-François Breton, 34093 Montpellier, France 11email: laure.berti@ird.fr Data Quality Profiling at Scale with Progressive Sampling: A Benchmark for Data-Centric AI Pipelines Laure Berti-Équille 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×1065× 10^6 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×≈40× worse at this budget), and across all real datasets DAG is 11–49× worse (Wilcoxon W=0W=0, p=0.002p=0.002, n=9n=9 independent pairs). Cluster sampling matches random uniform (MRE 0.110 vs. 0.111) with no added complexity; proxy-guided methods share the same failure mode as DAG (MRE 0.20–0.35). At scale, random uniform is near-linear (O(N0.964)O(N^0.964)) while DAG is super-linear (O(N1.272)O(N^1.272)), running 28–47× slower on ultra-large data with 6×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. 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, 15]. 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 near-real-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 hand-crafted 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 ≈3×10−6≈ 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 relative error 0.195–0.263 vs. 0.004–0.020; Wilcoxon W=0W=0, p=0.002p=0.002, n=9n=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=5MN=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%<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=0W=0, p=0.002p=0.002, n=9n=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(N0.964)O(N^0.964)) with stable 5.5–6.3% error from N=104N=10^4 to N=5×106N=5× 10^6, while DAG degrades to super-linear cost (O(N1.272)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ρ∈\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.03125p=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. 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)Q(D)=(q_1,q_2,q_3,q_4) is a 4-dimensional vector whose components are: 1. _missing\_rate: fraction of (row,col)(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.5IQR1.5\,IQR from Q1Q_1 or Q3Q_3 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 [5] and constituting a compact, interpretable summary for automated monitoring in DC-AI pipelines. Since computing Q(D)Q(D) exactly requires a full scan of D—prohibitive for large datasets—we instead estimate it from a sample ⊆DS D of size n=⌊b⋅N⌋n= b· N at budget fraction b∈(0,1]b∈(0,1]. Definition 2(Progressive Sampler) A progressive sampler A takes a budget fraction b∈(0,1]b∈(0,1] and returns a sample ⊆DS D of size ⌊b⋅N⌋ b· N . The estimated profile Q^()=(q^1,q^2,q^3,q^4) Q(S)=( q_1, q_2, q_3, q_4) approximates Q(D)Q(D). Definition 3(Relative Error) The mean relative error of an estimated profile Q^() Q(S) with respect to the ground truth Q(D)Q(D) is: rel_err(b)=14∑i=14min(|q^i−qi|max(qi, 0.05), 1.0).rel\_err(b)\;=\; 14 _i=1^4 \! ( | q_i-q_i| (q_i,\;0.05),\;1.0 ). The denominator is floored at 0.050.05 to avoid division by zero when a ground-truth indicator is near zero, and the ratio is capped at 1.01.0. The floor is set at 0.050.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|| q_i-q_i|, which we cap at 1.0 for robustness. Table 1: Summary of notation used throughout the paper. Symbol Meaning D Tabular dataset N=|D|N=|D| Number of rows M Number of columns b∈(0,1]b∈(0,1] Sampling budget fraction n=⌊bN⌋n= bN Sample size A Progressive sampler algorithm S Sample returned by A, ⊆DS D, ||=n|S|=n Q(D)Q(D) Exact quality profile (ground truth) Q^() Q(S) Estimated quality profile from sample (q1,…,q4)(q_1,…,q_4) Missing, duplicate, outlier, inconsistency rates qiq_i Per-row binary quality indicator σi _i Error-proxy score for row i wiw_i Horvitz–Thompson importance weight b0b_0 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| _c |>.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⌋n= bN rows uniformly at random without replacement from D. Each row has equal selection probability n/Nn/N; the quality estimate is an unweighted mean over the sample. Time complexity is O(N)O(N) per budget level. RU requires no schema knowledge, no metadata, and no prior profiling. Geometric. Batch sizes decrease geometrically: the first batch draws ⌊N/2⌋ N/2 rows, the second ⌊N/4⌋ 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)O(N) per batch. For datasets with N≥50,000N≥ 50,000 rows, the geometric sampler’s expected inter-row spacing N/nN/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 nY=⌊N1+Ne2⌋,e=0.05,n_Y= N1+Ne^2 , e=0.05, (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⌋)k= (10, N ) consecutive blocks of approximately equal size (by storage order) and draw ⌈b⋅k⌉ 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 per-row data quality without running the full profiler. For each numeric column c, the proxy score for row i is σi _i =1M∑c=1M[xic<Q1c−1.5IQRc = 1M _c=1^M1\! [x_ic<Q1_c-1.5\,IQR_c . ∨xic>Q3c+1.5IQRc] 40.00006pt . \;x_ic>Q3_c+1.5\,IQR_c ] +1M∑c=1M[xic is missing], + 1M _c=1^M1[x_ic is missing], (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(NM)O(NM) before sampling begins. 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×IQR1.5×IQR)111A sensitivity analysis on D2 and D4 datasets shows that a stricter 3×IQR3×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×IQR1.5×IQR as the default and note fence choice as a tunable design parameter., ensuring the proxy targets the same anomaly type it is asked to estimate. Metropolis-Hastings (MH). At each MCMC step, a batch of B=500B=500 candidate rows is drawn uniformly. Acceptance follows the Metropolis criterion with temperature λ=2.0λ=2.0. MH uses no dependency information; it steers proposals toward rows with higher error-proxy scores. Algorithm 1 DAG-Guided MCMC Sampler 0: Dataset D (N rows, M columns), budget b, batch size B, temperature λ, correlation threshold ρmin=0.3 _ =0.3 0: Importance-weighted sample ⊆DS D, weights w 1: Compute per-row proxy scores ←ErrorProxy(D) σ← ErrorProxy(D) 2: Build attribute DAG: add edge c→c′c→ c if |ρcc′|>ρmin| _c |> _ 3: Precompute column priority ←ClusterPriority(DAG)p← ClusterPriority(DAG) 4: Precompute column tail thresholds [lc,hc][l_c,h_c] at 5th/95th percentiles 5: Warm-start: draw B rows ∝ σ; let ←warm-startS -start 6: σ¯curr←mean([]) σ_curr ( σ[S]) 7: while ||<⌊bN⌋|S|< bN do 8: Sample pivot column c∗∼Categorical()c^* (p) 9: ←i∉:xic∗≤lc∗∨xic∗≥hc∗C←\i :x_ic^*≤ l_c^*\; \;x_ic^*≥ h_c^*\ 10: if =∅C= then 11: ←D∖C← D 12: end if 13: Draw proposal batch P⊆P , |P|=min(B,||)|P|= (B,|C|), uniformly 14: σ¯prop←mean([P]) σ_prop ( σ[P]) 15: if lnU<λ(σ¯prop−σ¯curr) U<λ\,( σ_prop- σ_curr), U∼Unif(0,1)U (0,1) (natural logarithm) then 16: ←∪PS ∪ P 17: else 18: ←∪UniformBatch(D∖,B/4)S (D ,\,B/4) 19: end if 20: Update σ¯curr σ_curr incrementally 21: end while 22: ←HTWeights([])w← HTWeights( σ[S]) 23: return S, w 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′c→ c is added whenever |ρcc′|>0.3| _c |>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λ=2.0). Algorithm 1 gives the full procedure.222This differs from MCMC in probabilistic databases [25], where chains are used for inference rather than row sampling. 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 _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=1max(σi,ε0),ε0=10−6,w_i= 1 ( _i,\, _0), _0=10^-6, (3) normalised so that ∑iwi=1 _iw_i=1. We clip at the 95th percentile of wi\w_i\ before normalisation. The final quality estimate is the weighted mean of per-row indicators: Q^()=∑i∈wiqi∑i∈wi. Q(S)= _i w_i\,q_i _i w_i. (4) Static samplers (RU, Geometric, Yamane) use uniform weights (wi=1/||w_i=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,000N≥ 50,000 (Section 2.1). Gibbs is described for theoretical completeness but excluded from these accuracy experiments: its O(NM)O(NM) 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 experiment E2, which provides directional—but underpowered (n=5n=5 seeds)—evidence on small synthetic data (contribution C6, open finding). Algorithm 2 ProgressiveProfiler 0: dataset D (N rows), sampler A, quality metrics Q, convergence threshold ε , initial fraction b0b_0, growth factor γ, patience k 0: quality profile P P, convergence round t∗t^*, final sample size n∗n^* 1: n←⌊b0⋅N⌋n← b_0· N ; t←0t← 0; ←0stable← 0 2: if A is guided (MH / Gibbs / DAG) then 3: Pre-compute ←ErrorProxy(D) σ← 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: 0←Draw(D,n,,)S_0← Draw(D,\,n,\,A,\, σ); P^0←ComputeProfile(0,,0) P_0← ComputeProfile(S_0,\,Q,\,w_0) 9: while n<Nn<N and <kstable<k do 10: n←min(⌊γ⋅n⌋,N)n← ( γ· n ,\,N); t←t+1t← t+1 11: t←Draw(D,n,,)S_t← Draw(D,\,n,\,A,\, σ) 12: P^t←ComputeProfile(t,,t) P_t← ComputeProfile(S_t,\,Q,\,w_t) 13: Δ←maxq∈|P^t[q]−P^t−1[q]|max(P^t−1[q],δ) ← _q | P_t[q]- P_t-1[q]| ( P_t-1[q],\;δ) 14: if Δ<ε < then 15: ←+1stable +1 16: else 17: ←0stable← 0 18: end if 19: end while 20: return P^t P_t, t∗←t^*← t, n∗←n^*← n In the benchmark experiments b0=0.05b_0=0.05, γ=2γ=2, ε=0.01 =0.01, and k=1k=1. Table 2: Comparison of the ten progressive sampling strategies (N: dataset size; M: columns; B: batch size; “Schema?”: requires FD rules). Method Information used Per-step cost Schema? Random Uniform None (uniform) O(N)O(N) No Geometric None (schedule) O(N)O(N) No Yamane Desired margin e O(N)O(N) one-shot No Cluster None (random blocks) O(N)O(N) No Metropolis-H. IQR proxy scores O(NM)O(NM) init ++ O(B)O(B)/step No Gibbs Column distribution O(NM)O(NM) init ++ O(B)O(B)/step No DAG IQR proxy ++ DAG O(NM+E)O(NM+E) init ++ O(B)O(B)/step No∗ Strat.-Col. Col. type ++ IQR proxy O(NM)O(NM) init ++ O(B)O(B)/draw No Strat.-Quality IQR proxy quantiles O(NM)O(NM) init ++ O(B)O(B)/draw No Importance IQR proxy (weighted) O(NM)O(NM) init ++ O(B)O(B)/draw No ∗DAG builds the dependency graph from data correlations; no external schema required. 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γ=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. 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(N0.964)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≈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 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 Cols Miss.% Out.% Role D1 NumPy synthetic tabular 100,000 8 5.0 5.0 Primary (controlled) D2 NYC 311 service requests 500,000 9 9.4 3.4 Primary (real admin.) D3 NYPD Arrest Data 500,000 18 .600 15.9 Primary (real admin.) D4 UCI Adult census income 48,842 14 .900 36.1† Primary (non-NYC) D5 Adult-derived synthetic 10K–5M 15 var.§ var.§ Scalability only D6-A Ultra-Marathon Running [18] 7,461,195 13 26.6 10.5 XXL real D6-B NYC Yellow Taxi Jan–Feb 2023 5,980,721 19 .600 .000 XXL real D7-synth IoT synthetic (IoTSensorGen.) 510,000 11 5.4 16.0 IoT D7-real Intel Berkeley Lab sensors [29] 2,313,156 11 .400 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ρ∈\.300,.500,.700,.900\ C7 RU <<1% error on IoT; DAG IQR collapse E8 D7-synth (510K); D7-real (2.3M) 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 non-administrative, non-NYC dataset, providing a domain-generalization check. D7-real (Intel Berkeley Research Lab, 2004) consists of 2.3M readings from 54 temperature/humidity/light/voltage sensors deployed over four months; its quality 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,000N≥ 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.50b∈\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,000B=1,000 for performance; all other experiments used the default B=500B=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=9n=9 independent pairs (3 seeds × 3 real datasets D2–D4). Table 5 reports mean relative error per method and dataset. 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 .401 .004 .019 .020 .111 geom. .401 .004 .019 .020 .111 yamane .465 .095 .055 .068 .170 dag .524 .195 .213 .263 .299 MH .526 .191 .210 .269 .299 cluster .407 .007 .009 .017 .110 strat-q .635 .004 .019 .156 .204 strat-col .635 .421 .245 .102 .351 importance .609 .238 .213 .190 .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=9n=9 independent pairs: dag vs. RU, W=0W=0, p=0.002p=0.002. cluster=0.110 ≈ RU; strat-q=0.204 (D4 gap: 0.156 vs. 0.020). 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×≈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).333Five 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. 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 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≈ 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 .050 .027 No Duplicate rate .025 .285 Yes Outlier rate .025 1.000 (cap) Yes FD-inconsistency rate .015 .294 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. 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 Miss Out Miss Out RU .002 .015 .000 .074 cluster .008 .020 .000 .035 yamane .007 .374 .003 .215 dag .099 .682 .007 .846 MH .092 .674 .007 .835 geom. .002 .015 .000 .074 strat-col 1.000 .682 .023 .957 strat-q .002 .015 .000 .074 importance .271 .682 .007 .846 3.3 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 .005 .007 .004 .003 .003 dag .195 .196 .196 .195 .194 D3 (NYPD) RU .037 .024 .020 .010 .001 dag .213 .213 .213 .213 .213 D4 (Adult) RU .027 .025 .021 .018 .011 dag .273 .274 .260 .262 .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% 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). Figure 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. Figure 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. 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%. 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 .365 .065 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). (a) (b) (c) Figure 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. 3.5 E5 — Scalability We profile D5 at five scales N∈10K,100K,500K,1M,5MN∈\10K,100K,500K,1M,5M\444The 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. and fit a power law T=aNα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ρ∈\0.3,0.5,0.7,0.9\ (5 seeds per ρ, b=0.50). Table 11 reports mean relative error per method and ρ. 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α/4=0.0125); the result is reported as open/inconclusive (C6). ρ dag gibbs MH p(dag<<MH), n=5 .300 .560 .553 .601 .031 .500 .540 .540 .594 .031 .700 .542 .534 .602 .031 .900 .556 .554 .598 .031 Mean .550 .545 .599 – p=0.03125 (=1/25=1/2^5) is the minimum 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. 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.031251/2^5=0.03125, which does not meet the Bonferroni-corrected threshold (α/4=0.0125α/4=0.0125). We treat this as inconclusive directional evidence requiring n≥20n≥ 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. 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 1.27 .560 2.03 1.10 .710 dag 18.3 23.9 24.3 25.5 25.4 D6-B (6.0M) RU .420 .350 .200 .110 .060 dag 17.4 17.3 17.2 17.4 17.6 Wall-clock time (s, mean over 10 seeds) D6-A (7.4M) RU .240 .380 .800 1.46 2.72 dag 8.92 12.24 22.19 40.63 79.38 D6-B (6.0M) RU .160 .260 .610 1.24 2.10 dag 14.57 17.90 27.58 42.96 74.77 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=5MN=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 23.5 12.2 .230 .180 geom. 23.5 12.2 .230 .180 yamane 28.5 28.5 1.33 1.33 cluster 23.5 11.9 2.36 .470 dag 72.6 59.7 26.9 26.9 MH 71.9 57.6 26.8 26.9 strat-q 53.0 45.0 .230 .180 strat-col 53.0 45.0 22.8 22.8 importance 48.5 35.7 19.0 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×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 IQR-proxy-stratified methods (strat-q: 45–53%) by a factor of 2–4. With n=3 seeds, the minimum achievable one-sided Wilcoxon p-value is 1/23=0.1251/2^3=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×≈117×) are large enough to be practically unambiguous, but formal statistical confirmation requires n≥7n≥ 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≈ 3× 10^-6 against a true rate of 29.6%, contributing a per-indicator relative error of ≈1.0≈ 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 [15]. Horvitz-Thompson weighting instability. When row scores cluster near zero (string-heavy datasets), importance weights wi∝1/scoreiw_i 1/score_i diverge toward 10610^6. 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%b=5\% on D2, dag_uniform achieves 30.5% MRE—worse than full dag (19.6%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 the weighting mechanism over the proposal bias is therefore budget-dependent: it is negligible at b≤5%b≤ 5\% and pronounced at b≥10%b≥ 10\% (daguniform =3.8%=3.8\% vs. dag =19.5%=19.5\% at b=50%b=50\%). This motivates a refined root-cause framing: the IQR weighting step is the dominant failure source at operational budgets (b≥10%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,1000B∈\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 cherry-picked 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 .196 .305 .005 D2 (NYC 311) 50 .195 .038 .003 D3 (NYPD) 5 .213 .024 .037 D3 (NYPD) 50 .213 .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 non-uniform 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≈ 3× 10^-6, yielding ≈1.0≈ 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 MCMC-specific: 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(N1.272)O(N^1.272) empirically). At N=5MN=5M rows this is 169 s against RU’s 14.3 s (12× slowdown with 6× worse 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), pre-training (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 proxy-guided method adds overhead without benefit. The decisive property for multi-indicator 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≥20n≥ 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. 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. [6] 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 [7]—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 [14]; 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 importance-weighted 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] dynamically 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 [4], has renewed interest in profiling pipelines and raised the expectation that structure-aware, dependency-guided 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 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=5N=5M; stratified and importance-weighted methods that rely on IQR-based proxies inherit the same structural failure (strat-col 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)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 data-centric lesson: when a hand-crafted proxy (IQR score) guides a sampler (MCMC chain), the proxy’s coverage determines the system’s utility. In tabular DC-AI 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×1065× 10^6 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 DAG-guided sampling helps on genuinely structured relational or knowledge-graph data requires replacing the random stub with a real dataset and running E2 at n≥20n≥ 20 seeds per ρ level [9]. Stratified sampling with a proxy that captures categorical quality defects (not IQR-based) remains an open avenue. credits 6.0.1 Acknowledgements This work was carried out at IRD, ESPACE-DEV, Montpellier, France. 6.0.2 The author has no competing interests to declare that are relevant to the content of this article. References [1] Z. Abedjan, X. Chu, D. Deng, R. C. Fernandez, I. F. Ilyas, M. Ouzzani, P. Papotti, M. Stonebraker, and N. Tang (2016) Detecting data errors: where are we and what needs to be done?. In VLDB, Vol. 9, p. 993–1004. External Links: Document Cited by: §1, §2.2, §2.2, §5, §5. [2] Z. Abedjan, L. Golab, and F. Naumann (2015) Profiling relational data: A survey. VLDB Journal 24 (4), p. 557–581. External Links: Document Cited by: §1, §1, §3.1, §5. [3] S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica (2013) BlinkDB: queries with bounded errors and bounded response times on very large data. In EuroSys, p. 29–42. External Links: Document Cited by: §5. [4] L. Berti-Équille, A. Bonifati, and T. Milo (2018) Machine learning to data management: A round trip. In 34th IEEE International Conference on Data Engineering (ICDE), p. 1735–1738. External Links: Document Cited by: §5. [5] L. Berti-Équille, I. Comyn-Wattiau, M. Cosquer, Z. Kedad, S. Nugier, V. Peralta, S. S. Cherfi, and V. Thion-Goasdoué (2011) Assessment and analysis of information quality: a multidimensional model and case studies. International Journal of Information Quality 2 (4), p. 300–323. External Links: Document Cited by: §1.1. [6] L. Berti-Équille, H. Harmouch, F. Naumann, N. Novelli, and S. Thirumuruganathan (2018) Discovery of genuine functional dependencies from relational data with missing values. Proceedings of the VLDB Endowment (PVLDB) 11 (8), p. 880–892. External Links: Document Cited by: §5. [7] L. Berti-Équille (2007) Data quality awareness: a case study for cost optimal association rule mining. Knowledge and Information Systems 11 (2), p. 191–215. External Links: Document Cited by: §5. [8] X. Bouthillier, P. Delaunay, M. Bronzi, A. Trofimov, B. Nichyporuk, J. Szeto, N. Sepah, E. Raff, K. Madan, V. Voleti, S. E. Kahou, V. Michalski, D. Serdyuk, T. Arbel, C. Pal, G. Varoquaux, and P. Vincent (2021) Accounting for variance in machine learning benchmarks. In MLSys, External Links: Document Cited by: §4. [9] K. S. Button, J. P. A. Ioannidis, C. Mokrysz, B. A. Nosek, J. Flint, E. S. J. Robinson, and M. R. Munafò (2013) Power failure: why small sample size undermines the reliability of neuroscience. Nature Reviews Neuroscience 14 (5), p. 365–376. External Links: Document Cited by: §6. [10] G. Cormode, M. Garofalakis, P. J. Haas, and C. Jermaine (2011) Synopses for massive data: samples, histograms, wavelets, sketches. Foundations and Trends in Databases 4 (1–3), p. 1–294. External Links: Document Cited by: §5. [11] P. S. Efraimidis and P. G. Spirakis (2006) Weighted random sampling with a reservoir. In Information Processing Letters, Vol. 97, p. 181–185. External Links: Document Cited by: §5. [12] S. Grafberger, P. Groth, J. Stoyanovich, and S. Schelter (2022) Data distribution debugging in machine learning pipelines. VLDB Journal 31, p. 1103–1126. External Links: Document Cited by: §5. [13] P. J. Haas and J. M. Hellerstein (1999) Ripple joins for online aggregation. In SIGMOD, p. 287–298. External Links: Document Cited by: §5. [14] J. M. Hellerstein, P. J. Haas, and H. J. Wang (1997) Online aggregation. In SIGMOD, p. 171–182. External Links: Document Cited by: §5. [15] J. M. Hellerstein (2008) Quantitative data cleaning for large databases. Technical report United Nations Economic Commission for Europe (UNECE). External Links: Link Cited by: §1, §4. [16] D. G. Horvitz and D. J. Thompson (1952) A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association 47 (260), p. 663–685. External Links: Document Cited by: §2.3. [17] G. H. John and P. Langley (1996) Static versus dynamic sampling for data mining. In KDD, p. 367–370. External Links: Link Cited by: §1, §5. [18] Kaggle (2021) The big dataset of ultra-marathon running. Kaggle. Note: https://w.kaggle.com/datasets/aiaiaidavid/the-big-dataset-of-ultra-marathon-running/dataAccessed: May 2026 External Links: Link Cited by: Table 3. [19] M. Mazumder, C. Banbury, X. Yao, B. Karlaš, W. G. Rojas, S. Diamos, G. Diamos, L. He, A. Parrish, H. R. Kirk, et al. (2023) DataPerf: benchmarks for data-centric AI development. In Advances in Neural Information Processing Systems 36 (NeurIPS), Datasets and Benchmarks Track, External Links: Document Cited by: §1, §5. [20] F. Naumann and M. Herschel (2010) An introduction to duplicate detection. Morgan & Claypool Publishers. External Links: Document Cited by: §5. [21] J. Neyman (1934) 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), p. 558–625. External Links: Document Cited by: §5. [22] Y. Park, B. Mozafari, J. Sorenson, and J. Wang (2018) VerdictDB: universalizing approximate query processing. In SIGMOD, p. 1461–1476. External Links: Document Cited by: §5. [23] H. Patel, S. Guttula, R. S. Mittal, N. Manwani, L. Berti-Équille, and A. Manatkar (2022) Advances in exploratory data analysis, visualisation and quality for data centric AI systems. In KDD, p. 4814–4815. External Links: Document Cited by: §5. [24] F. Provost, D. Jensen, and T. Oates (1999) Efficient progressive sampling. In KDD, p. 23–32. External Links: Document Cited by: §1, §2.5, §5. [25] C. Ré and D. Suciu (2008) Approximate lineage for probabilistic databases. PVLDB 1 (1), p. 797–808. External Links: Document Cited by: §1, footnote 2. [26] T. Rekatsinas, X. Chu, I. F. Ilyas, and C. Ré (2017) HoloClean: holistic data repairs with probabilistic inference. In VLDB, Vol. 10, p. 1190–1201. External Links: Document Cited by: §5. [27] S. Schelter, D. Lange, P. Schmidt, M. Celikel, F. Biessmann, and A. Grafberger (2018) Automating large-scale data quality verification. Proceedings of the VLDB Endowment (PVLDB) 11 (12), p. 1781–1794. External Links: Document Cited by: §5. [28] S. K. Thompson (1990) Adaptive cluster sampling. Journal of the American Statistical Association 85 (412), p. 1050–1059. External Links: Document Cited by: §5. [29] G. Tolle, J. Polastre, R. Szewczyk, D. Culler, N. Turner, K. Tu, S. Burgess, T. Dawson, P. Buonadonna, D. Gay, and W. Hong (2005) A macroscope in the redwoods. In Proc. 3rd ACM Conference on Embedded Networked Sensor Systems (SenSys), Note: Intel Berkeley Research Lab dataset: http://db.csail.mit.edu/labdata/ External Links: Document Cited by: §1, §3.8, Table 3. [30] J. S. Vitter (1985) Random sampling with a reservoir. ACM Transactions on Mathematical Software 11 (1), p. 37–57. External Links: Document Cited by: §5. [31] S. E. Whang, Y. Roh, H. Song, and J. Lee (2023) Data collection and quality challenges in deep learning: a data-centric AI perspective. VLDB Journal 32 (4), p. 791–813. External Links: Document Cited by: §1, §5. [32] T. Yamane (1967) Statistics: an introductory analysis. 2nd edition, Harper and Row, New York. External Links: ISBN 9780060473136, Link Cited by: §2.1. [33] D. Zha, Z. P. Bhat, K. Lai, F. Yang, Z. Jiang, S. Zhong, and X. Hu (2025) Data-centric artificial intelligence: a survey. ACM Computing Surveys 57 (5). External Links: Document Cited by: §1, §5. [34] Y. Zhu (2025) Efficient approximate query processing with block sampling. In Conference on Innovative Data Systems Research (CIDR), External Links: Link Cited by: §5.