{"id":"e4085e7f-e29b-48cd-84ee-a273597218ed","arxiv_id":"2607.10771","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Optimized HyMD in Desbordante discovers matching dependencies >40× faster on average (up to 170×) via focused sampling, faster generalization checks, and denser LHS representation.","lead":"The paper speeds up discovery of matching dependencies (similarity-aware functional dependencies) by optimizing the HyMD algorithm and shipping a C++ implementation in Desbordante. Average speedups exceed 40\times (up to 170×) versus the prior Java prototype, with Python bindings for custom similarity functions.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly flags the sampling heuristic as the least-theoretically-supported component, yet over-states the risk: the heuristic cannot miss minimal MDs because lattice validation is complete and always terminates the algorithm. The only residual uncertainty is whether the same schedule remains faster on unseen data distributions; that is an ordinary empirical caveat for a systems paper, not a threat to the reported 40×–170× results or to reproducibility. Consequently the ACCEPT verdict and high confidence stand.","tokens_in":17644,"tokens_out":371,"duration_ms":35414,"concrete_test":"Run both Metanome HyMD and Desbordante-optimized HyMD on the seven evaluation tables, dump the sets of minimal MDs (cardinality, support, decision-boundary vectors), and confirm set equality; any discrepancy larger than floating-point noise would falsify the “same dependencies” part of the claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim (Tables V–VI) holds under the reported head-to-head measurements: the three listed optimizations plus the C++ reimplementation produce the stated speed-ups while the final lattice-traversal phase still enumerates exactly the minimal interesting MDs. Focused sampling and the adapted stop heuristic (Section V-A) affect only the hybrid schedule’s efficiency; they cannot omit a minimal MD because every remaining candidate is exhaustively validated against the full data before termination. The absence of a theoretical optimality proof for the 0.01-threshold schedule is therefore not load-bearing for correctness or for the measured speed-ups on the seven tables. Open-source code further allows independent confirmation of output identity.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","summary":"The paper presents an industrial-grade C++ reimplementation of the HyMD algorithm for discovering matching dependencies (MDs), integrated into the Desbordante profiler. It contributes three main optimizations—focused sampling by column match (Section V-A), a faster generalization-lookup that exploits lattice minimality (Section V-B), and a denser LHS representation using (offset, similarity) pairs (Section V-C)—plus several technical improvements (decision-boundary indices, empty-node pruning, column-match ordering). Head-to-head experiments on seven public datasets against the original Metanome Java HyMD report average wall-clock speed-ups >40\times (up to 170\times on CORA) and substantial memory reductions (Tables V–VII), while the final lattice-traversal phase still enumerates the same minimal interesting MDs. Bidirectional Python bindings allow custom similarity functions.","tokens_in":17785,"tokens_out":768,"duration_ms":11769,"significance":"Matching dependencies are among the most expressive data-quality patterns; their discovery has remained largely impractical because of exponential lattice size and quadratic pair enumeration. Delivering a ready-to-use, open-source C++ implementation that is more than an order of magnitude faster than the previous state-of-the-art prototype, together with Python integration for custom metrics, materially lowers the barrier to applying MDs in entity resolution, deduplication and schema matching. The empirical evidence is concrete (public baseline, public datasets, reproducible code) and the optimizations are described with enough algorithmic detail to be re-implemented or further improved. The work therefore constitutes a solid engineering and systems contribution that advances practical data profiling.","major_comments":[],"minor_comments":[{"comment":"Section V-A: the initial efficiency threshold of 0.01 and the lattice-stop fraction are presented as fixed heuristics. A short sensitivity paragraph (or an appendix table) showing how runtime and MD count change under modest variations would strengthen confidence that the schedule is robust.","section":null},{"comment":"Table VI: preprocessing times improve even for the “vanilla” Desbordante rewrite; a one-sentence clarification that the gain comes mainly from faster metric implementations (rather than algorithmic changes) would avoid mis-attribution.","section":null},{"comment":"Figures 6–7: the dual y-axes (time vs. number of MDs) are useful, yet the caption should explicitly state that the MD counts are those of the optimized implementation, so readers do not wonder whether the three versions produce identical cardinalities.","section":null},{"comment":"Section VII: the claim that more than half of execution time is spent waiting for memory is plausible but unsupported by any profiler numbers; a brief citation of cache-miss or stall counters would make the future-work argument more concrete.","section":null},{"comment":"Throughout: a few typographical inconsistencies remain (“Levenstein” vs. “Levenshtein”, “undecillions”, occasional missing articles). A final proof-reading pass would polish the presentation.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a high-quality systems paper whose central empirical claim is solidly supported. The absence of a theoretical optimality proof for the sampling schedule is not load-bearing for correctness, as the final exhaustive lattice traversal guarantees completeness. I see no reason to delay acceptance; the minor presentation points can be handled in camera-ready."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a clean engineering paper that takes the TODS 2020 HyMD algorithm, reimplements it in C++ inside Desbordante, and adds three practical improvements: focused sampling by column match (adapted from HyFD), a lattice-node skip that exploits minimality when checking generalizations, and a sparse (offset, threshold) LHS representation. The measured result is more than 40× average wall-clock speedup over the public Metanome Java baseline, peaking above 170× on CORA, with memory usually down by an order of magnitude. Tables V–VI break out preprocessing versus execution; the same minimal interesting MDs are produced. Code and Python bindings are already public, so the claim is independently checkable.\n\nWhat is new is therefore not the hybrid lattice-plus-inference skeleton, but the concrete schedule and data-structure changes that make the schedule work well on real tables, plus the industrial packaging. The sampling heuristic (start at 0.01 efficiency, relax later, prioritize high-similarity pairs via the similarity-index array) has no optimality proof, yet the paper is careful: every surviving candidate is still exhaustively validated in the final lattice-traversal phase, so completeness is preserved. That is enough for a systems contribution.\n\nSoft spots are minor and proportional. The seven datasets are standard but small; scaling plots stop at a few tens of thousands of rows and a few dozen columns. Preprocessing still dominates on some tables, and the authors themselves note that similarity-index memory remains a bottleneck for larger collections. None of these undermine the central empirical claim.\n\nAnyone building data profilers, MDM tools, or entity-resolution pipelines who needs matching dependencies will get immediate value. The math is standard lattice theory; the citations are honest; the experiments are head-to-head and reproducible. I would send it to referees without hesitation and would cite the artifact myself when I next need an MD miner.","headline":"Solid systems paper: real 40–170× speedups on HyMD via focused sampling, lattice pruning, and denser LHS encoding, shipped with open C++/Python code.","tokens_in":18418,"tokens_out":491,"would_cite":true,"duration_ms":7721,"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":"Focused sampling and denser lattice structures make matching-dependency discovery more than 40\times faster on average, up to 170\times on hard datasets.","keywords":["matching dependencies","dependency discovery","hybrid algorithms","data profiling","entity resolution","lattice search","similarity indexes"],"falsifier":"Run both the optimized and reference implementations on a previously unseen real-world table that contains many near-duplicates but few exact equals (or on a synthetic table engineered to violate the 0.01 efficiency threshold) and check whether the sets of returned minimal matching dependencies differ or the speedup collapses below 2×.","tokens_in":18554,"feed_emoji":"⚡","tokens_out":600,"duration_ms":9580,"temperature":0.7,"pith_summary":"Matching dependencies say that if certain attribute values are similar under user-chosen metrics, other attributes must also be similar. They are powerful for entity resolution, deduplication and data cleaning, but discovery is exponential and previously limited to research prototypes. This paper shows that three concrete changes to the state-of-the-art hybrid algorithm—column-match-focused sampling that prefers high-similarity pairs, skipping irrelevant lattice nodes when testing generalizations, and a sparse left-hand-side representation—raise practical speed by more than 40\times on average (and more than 170\times on a classic bibliographic dataset) while still returning exactly the same minimal interesting dependencies. The resulting C++ implementation ships with a Python interface that accepts custom similarity functions, so the technique can be used today rather than remaining a laboratory curiosity.","feed_headline":"Matching-dependency discovery now 40\times faster on average","feed_subtitle":"Focused sampling and denser lattices turn a research prototype into practical Python tooling","key_machinery":"Focused sampling by column match: records are ordered via pre-built similarity indexes so that pairs with higher similarity are examined first; efficiency is measured by the ratio of violating pairs and the algorithm switches phases only when that ratio falls below a relaxing threshold, keeping the lattice near its final state.","core_discovery":"Re-engineering the hybrid HyMD algorithm with focused sampling that prioritizes high-similarity record pairs, an invariant-based generalization check that ignores already-known non-generalizing lattice nodes, and a pointer-friendly sparse representation of left-hand sides yields more than 40\times average wall-clock speedup (peaking above 170\times) over the prior Java reference while discovering identical minimal interesting matching dependencies.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Matching deps discovery now over 40x faster on average","Focused sampling and lattices cut HyMD time by 40x+","Desbordante HyMD hits 40x average speedup on matching deps","New sampling and sparse LHS give HyMD over 40x wall-clock gains","Matching dependency mining sped up 40x average, 170x peak"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The new sampling heuristic and phase-switch rule remain complete and efficient on tables outside the seven evaluated datasets; the paper supplies no theoretical guarantee that the schedule never misses a minimal dependency or becomes pathologically slow.","fun_headline_variants_meta":{"raw":{"variants":["Matching deps discovery now over 40x faster on average","Focused sampling and lattices cut HyMD time by 40x+","Desbordante HyMD hits 40x average speedup on matching deps","New sampling and sparse LHS give HyMD over 40x wall-clock gains","Matching dependency mining sped up 40x average, 170x peak"]},"model":"grok-4.5","effort":"low","cost_usd":0.006098,"raw_usage":{"total_tokens":1561,"prompt_tokens":817,"num_sources_used":0,"completion_tokens":96,"cost_in_usd_ticks":60980000,"prompt_tokens_details":{"text_tokens":817,"audio_tokens":0,"image_tokens":0,"cached_tokens":0},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":648,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":817,"tokens_out":96,"duration_ms":8140,"temperature":1.0,"reasoning_tokens":648,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T09:22:05.267184+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run both the optimized and reference implementations on a previously unseen real-world table that contains many near-duplicates but few exact equals (or on a synthetic table engineered to violate the 0.01 efficiency threshold) and check whether the sets of returned minimal matching dependencies differ or the speedup collapses below 2×.","supporting_citations":[],"review_version":1}