{"id":"8bd9a648-23ed-46fe-86a5-6151356a7efa","arxiv_id":"2607.23632","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.5,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"C++ reimplementations plus range-based partitions and Boost structures speed FASTOD/ORDER OD discovery up to 10× and cut memory up to 2.9× versus Java baselines.","lead":"The authors reimplemented two order-dependency discovery algorithms (FASTOD and ORDER) in C++ inside Desbordante and added partition and data-structure optimizations. The result is up to 10× faster runtimes and 2.9× lower memory than the prior Java prototypes, moving OD mining closer to practical use.","discovery_kind":"new_method","skeptic_critique":null,"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper presents C++ reimplementations of two order-dependency (OD) discovery algorithms — FASTOD (set-based axiomatization) and ORDER (list-based) — inside the open-source Desbordante profiler, plus two classes of optimizations: (i) a range-based stripped-partition representation for FASTOD with a preprocessing-time selection heuristic and a dynamic switch back to the standard representation, governed by three constants; and (ii) Boost-based replacements (flat stable sort / block indirect sort, unordered flat set/map) for ORDER's hot paths. Experiments against the original Java implementations on 15 (FASTOD) and 7 (ORDER) real datasets report speedups of up to ~10x total and memory reductions of up to ~2.9x, with three-run averages, scalability plots over column count, and breakdowns of baseline-vs-optimized contributions. The paper also gives a tutorial-style treatment of both OD axiomatizations and an honest account of ORDER's incompleteness relative to FASTOD.","tokens_in":18821,"tokens_out":9158,"duration_ms":332094,"significance":"If the numbers hold up after the requested audit, this is a useful systems contribution: it ships what appear to be the only open-source C++ implementations of ORDER and FASTOD, merged into Desbordante (PRs 294, 355), with a public data repository — a genuine reproducibility asset. The range-based stripped partition with adaptive switch-over is a clean, reusable data-structure idea with applicability to other partition-based dependency-discovery algorithms. The evaluation is broad (15 FASTOD and 7 ORDER datasets) and commendably honest in places: the authors report that the optimized variant uses more memory than the baseline (Table VI) and that Java wins on one ORDER dataset (Table VIII). These are the marks of a credible empirical study, and the claimed gains (up to ~10x time, ~2.9x memory) would matter for practical OD discovery.","major_comments":[{"comment":"Abstract/§VI vs. Tables V, VI, VIII: the headline numbers are internally inconsistent. The abstract claims 'up to 3x' for reimplementation, 'up to 10x' with techniques, and 'up to 2.9x' memory. Table V shows FASTOD base-vs-Java up to 7.77x (S1) and total up to 10.16x (D1); §V-B Exp. 1 says 'up to 8, average 4'; Table VIII shows ORDER total up to 24.06x (Modis); Table VI shows Java-vs-base memory up to 14.96x (D2). The abstract matches none of these. Since the speed-up factors are the paper's central claim, all quoted numbers must be reconciled with the tables.","section":"Abstract; Tables V–VIII"},{"comment":"Theorem 2.2 ('X↦→< Y iff X↦→≤ Y') is false as stated: on r = {(1,1),(1,2)} over single attributes X,Y the strict OD holds vacuously (no pair satisfies sX < tX) while the ≤-OD is violated by the split. This also contradicts the paper's own §II-C statement that splits invalidate only ≤/≥ ODs. Relatedly, Example 2.2/2.4 asserts FD {Weight}→{Shipment cost} holds in Table I, but tuples t2 (15,48) and t4 (15,28) — the very split cited in Ex. 2.4 — violate that FD. The intended FD-vs-OD teaching point requires a corrected example.","section":"§II, Theorem 2.2, Examples 2.2/2.4"},{"comment":"JVM methodology is unspecified, yet the 'ME'/∞ entries in Tables V–VI and the claim that Java runs out of RAM are load-bearing for the memory-savings story. Default -Xmx is typically a fraction of physical RAM, so a heap error does not establish 'not enough RAM on the computer.' Report JVM flags (-Xmx, GC), warmup handling, and how peak memory was measured on both sides; otherwise the ∞ rows and the memory ratios are not interpretable.","section":"§V-A/B, Experimental Setup"},{"comment":"No correctness validation of the reimplementations is reported. The paper never states that the C++ FASTOD/ORDER outputs are identical to the Java references' outputs (or that optimized and baseline C++ agree). Table IV's #OD/#FD/#OCD columns suggest result counts are available — please state explicitly whether dependency sets match the Java baselines on the integer-transformed datasets. For a paper whose premise is faithful reimplementation, this check is essential.","section":"§IV-D, §V"},{"comment":"The three constants governing the range-based partition (range-forming proportion 0.001, small-range cutoff 40, switch-over ratio 0.5) are asserted without justification or sensitivity analysis. RQ3's no-degradation claim and the adaptive-switch behavior rest on these values. A small sensitivity sweep on two or three datasets (or a principled selection procedure) would substantiate that the technique is robust rather than tuned to the evaluation suite.","section":"§IV-E"}],"minor_comments":[{"comment":"Table II: the combined speedup exceeds the product of the individual ones (Diabetes: 1.017 × 4.954 × 0.969 ≈ 4.88 vs. 6.253 reported); 'sort' alone is a slowdown on Diabetes (0.969x); flat_set alone yields 4.95x only on Diabetes. The interaction effects deserve a sentence of analysis.","section":"§V-C, Table II"},{"comment":"Several ORDER runtimes are sub-second (Pfw optimized 0.209s, Diabetes optimized 0.591s) and each experiment is averaged over only three runs. Report standard deviations and consider more repetitions, since timer noise at this scale is comparable to the measured effects.","section":"§V-C"},{"comment":"Table VI, row D2: the 14.96x memory reduction is an outlier against 1.8–3.9x elsewhere and deserves an explanation (also the D2 dataset is 5 MB on disk while Java uses 1 GB).","section":"Table VI"},{"comment":"Dataset provenance is weak: Table IV names such as 'file.csv', 'Dataset norm.csv', and 'Test norm.csv' are uninformative. Please give sources, and describe the integer-encoding transformation applied for Java FASTOD, including whether it preserves partition/equivalence-class structure (otherwise the comparison could be skewed).","section":"§V-B, Table IV"},{"comment":"§V-C Exp. 1: Java beats the C++ baseline on Diabetes (0.901x). This is noted only as motivation for optimizations; a brief analysis of why the Java version wins here would strengthen the evaluation.","section":"§V-C"},{"comment":"Conclusion is garbled: 'ORDER is significantly faster than FASTOD, but misses some dependencies... ORDER, on the other hand, can be useful for quick profiling' — the second subject should presumably be FASTOD; the same confusion appears in §V-C.","section":"§VI"},{"comment":"Typos/notation: '80es' (§I), 'altough' (§III), 'out knowledge' (§III), 'XX\\{A,B}' in the C+/C− definitions (§IV-C), broken header layout in Table V, and barely legible bar labels in Figures 1–2. State the Boost version used in §IV-F.","section":"Throughout"},{"comment":"§III contrasts ORDER's O(|R|!) with FASTOD's O(2^|R|) and says FASTOD 'achieves greater performance', while §V-C shows ORDER is empirically much faster. Clarify that the complexity bounds concern lattice size, not observed runtime.","section":"§III"}],"recommendation":"major_revision","confidential_remarks":"The mismatch between the abstract's headline factors and the tables suggests the numbers were not updated after the final experiment pass; I would ask the authors to audit every quoted factor against Tables II–VIII. Self-citations are confined to the group's own Desbordante line of work and are appropriate context, not padding. The range-based partition idea is simple but appears new in this setting; I have no novelty concerns. Overall this is competent empirical systems work whose deficiencies are fixable in one revision round."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: they took ORDER and FASTOD, ported them cleanly into Desbordante’s C++ stack, and then actually fixed the hot paths. The new piece that matters is the range-based stripped partition for FASTOD—store runs instead of index lists, product via sorted range intersection (their Algorithm 1), and a dynamic switch back to the ordinary representation when ranges fragment. For ORDER they mostly swap in Boost sorts and flat hash containers. Measured gains are real: roughly 3× from the port alone, up to ~10× with the tricks, memory down ~2–3×, on a decent set of public tables, with open code already merged.\n\nThat is honest systems work. They keep the two axiomatizations distinct, admit ORDER’s incomplete pruning, separate baseline vs optimized, and show column-scaling plots. Correctness of the range form is by construction until the explicit switch; they are not inventing a new dependency class or changing asymptotics. For anyone who ships profilers or cares about making OD mining usable on mid-size tables, this is directly useful.\n\nSoft spots are proportionate and mostly engineering hygiene. Three constants (0.001 range fraction, size-40 “small”, 0.5 switch ratio) are hand-picked with no sensitivity study; that is the weakest assumption, not a correctness bomb. They report three-run averages without variance. Java vs C++ comparisons always carry some language noise, though they isolate algorithm time and the optimized C++ still beats their own baseline. Novelty is moderate—prior Desbordante papers already sold the “rewrite in C++” story—so the contribution lives in the partition representation and the concrete measurements, not in theory.\n\nMath and citations look fine: they track Langer/Naumann and Szlichta et al. correctly and do not overclaim completeness for ORDER. Who it is for: data-profiling and systems people who implement dependency miners. I would send it to peer review; a serious referee can push on the thresholds and ask for a bit more ablation, but the artifact and numbers already clear the bar. Engage if you care about practical OD tooling; skip if you only want new dependency theory.","headline":"Solid engineering paper: real C++ speed-ups and a useful range-based partition trick for OD mining, not a new theory result.","tokens_in":19555,"tokens_out":537,"would_cite":false,"duration_ms":19765,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Careful C++ reimplementation plus range-based partitions speeds order-dependency discovery up to 10× and cuts memory up to 2.9×.","keywords":["order dependency","OD discovery","FASTOD","ORDER","data profiling","stripped partitions","range-based partitions","implementation optimization"],"falsifier":"Run the optimized FASTOD side-by-side with the plain C++ baseline on a large table whose run-length distribution sits near the three switch thresholds; if the optimized version is slower or more memory-hungry while still returning the identical dependency set, the claimed gains do not generalize.","tokens_in":19840,"feed_emoji":"⚡","tokens_out":757,"duration_ms":36684,"temperature":0.7,"pith_summary":"Order dependencies capture the fact that sorting a table by one list of columns also sorts it by another; they matter for query optimization, cleaning, deduplication, and anomaly detection. Prior work treated discovery purely as an algorithmic problem and shipped only Java research prototypes, leaving a large engineering gap on a task that is already computationally heavy. This paper reimplements the two main miners—ORDER (list-based, incomplete but fast) and FASTOD (set-based, complete)—in C++, then attacks their real bottlenecks with new data-structure techniques. The central result is that implementation choices alone move OD discovery much closer to practical, industrial use.","feed_headline":"OD miners run up to 10× faster with range partitions","feed_subtitle":"C++ rewrites plus smarter equivalence-class storage cut runtime and memory for order-dependency discovery.","key_machinery":"Range-based stripped partitions: equivalence classes are stored as contiguous index ranges rather than full index lists, chosen automatically when a column has enough runs, intersected by a fast range-product algorithm, and switched back to ordinary lists once ranges become too fragmented.","core_discovery":"Simply rewriting ORDER and FASTOD in C++ already yields up to roughly 3× lower runtime and substantially less memory than the original Java prototypes; adding the authors’ targeted techniques—especially a range-based representation of stripped partitions for FASTOD and faster containers and sorts for ORDER—raises total speed-ups to as much as 10× while reducing memory consumption by up to 2.9×.","pith_inferences":["The same range-compression idea is likely to help other partition-heavy dependency miners such as functional-dependency and denial-constraint algorithms.","The three hand-chosen constants point to a natural next step: an adaptive or learned policy for choosing and switching representations.","A hybrid pipeline that runs fast incomplete ORDER first as a pre-filter before complete FASTOD is an untested but direct corollary of the two algorithms’ complementary strengths."],"forward_implications":["OD discovery becomes feasible on larger tables that previously exhausted time or RAM.","Other lattice miners that rely on equivalence-class partitions can reuse the same range representation.","Practitioners can pick ORDER for a fast incomplete sketch or FASTOD for a complete result, both now at usable speed.","Query optimizers and cleaning pipelines can afford OD checks more frequently."],"fun_headline_variants":["C++ rewrites cut OD discovery time up to 3× before extra techniques","Range partitions and faster sorts push OD miners to 10× speedups","FASTOD and ORDER use far less memory after Desbordante reimplementation","Stripped-partition ranges shrink FASTOD runtime and RAM footprint","Targeted container and sort fixes yield up to 2.9× lower OD memory use"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"Three fixed numeric thresholds that decide when to start with ranges and when to switch back work well on tables beyond the evaluation suite and never silently hurt correctness or cost.","fun_headline_variants_meta":{"raw":{"variants":["C++ rewrites cut OD discovery time up to 3× before extra techniques","Range partitions and faster sorts push OD miners to 10× speedups","FASTOD and ORDER use far less memory after Desbordante reimplementation","Stripped-partition ranges shrink FASTOD runtime and RAM footprint","Targeted container and sort fixes yield up to 2.9× lower OD memory use"]},"model":"grok-4.5","effort":"low","cost_usd":0.004063,"raw_usage":{"total_tokens":1283,"prompt_tokens":800,"num_sources_used":0,"completion_tokens":83,"cost_in_usd_ticks":40628000,"prompt_tokens_details":{"text_tokens":800,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":400,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":800,"tokens_out":83,"duration_ms":6952,"temperature":1.0,"reasoning_tokens":400,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T17:10:35.478657+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run the optimized FASTOD side-by-side with the plain C++ baseline on a large table whose run-length distribution sits near the three switch thresholds; if the optimized version is slower or more memory-hungry while still returning the identical dependency set, the claimed gains do not generalize.","supporting_citations":[],"review_version":1}