Auto-FuzzyJoin: Auto-Program Fuzzy Similarity Joins Without Labeled Examples
Auto-FuzzyJoin uses geometric distance interpretation for unsupervised parameter inference, significantly improving fuzzy-join quality.
Key Findings
Methodology
Auto-FuzzyJoin leverages a geometric interpretation of distance functions, integrating negative rule learning and multi-configuration union strategies. It automatically infers suitable fuzzy-join parameters without labeled data, by analyzing the reference table's low-duplicate property to estimate safe boundaries and avoid false positives. The framework maximizes recall while maintaining a target precision, using distance space properties to adaptively tune parameters. It employs a disjunctive program structure for interpretability and extensibility, enabling high-quality fuzzy-joins across diverse datasets. The approach is validated on 50 Wikipedia tasks, outperforming existing unsupervised methods and approaching semi-supervised models.
Key Results
- On 50 Wikipedia datasets, Auto-FuzzyJoin achieved an average recall of 85%, surpassing traditional unsupervised approaches by over 20%. When using 50% ground-truth labels, its performance closely matched supervised models like Magellan and DeepMatcher, demonstrating its effectiveness in semi-supervised settings.
- In benchmark tests, the method reached 92% accuracy, outperforming baselines especially in noisy and heterogeneous data scenarios. The geometric distance-based inference effectively balanced precision and recall, reducing false positives.
- Ablation studies confirmed that distance space interpretation and negative rule learning are crucial for optimal performance, with the union of multiple configurations further enhancing coverage.
Significance
This work addresses a longstanding challenge in entity resolution: automatic, high-quality fuzzy-join parameter tuning without supervision. By introducing a geometric distance framework, it reduces reliance on manual trial-and-error, making fuzzy-joins more accessible and reliable. The interpretability of the generated programs fosters trust and facilitates validation. Its robustness across diverse datasets paves the way for scalable, automated data integration, knowledge graph construction, and large-scale entity matching. The approach bridges the gap between unsupervised simplicity and supervised accuracy, promising broad impact in data engineering and AI-driven data management.
Technical Contribution
The paper introduces a novel geometric interpretation of distance functions, enabling unsupervised inference of safe thresholds and negative rules. It combines this with a multi-configuration union strategy, optimizing recall under a precision constraint. The framework's core innovation lies in leveraging the low-duplicate property of reference tables to estimate safe matching boundaries and learn negative rules, which significantly reduces false positives. The method's modular design allows easy extension to new distance functions and multi-column matching, providing a transparent, explainable alternative to black-box models. Theoretical analysis proves NP-hardness of the optimization problem, but the proposed heuristic achieves practical effectiveness.
Novelty
This research is the first to exploit the geometric properties of distance functions for automatic parameter inference in fuzzy-joins. Unlike prior supervised or heuristic-based methods, it offers a fully unsupervised, interpretable framework that adapts to data characteristics without labeled examples. The introduction of negative rule learning based on reference table analysis further distinguishes it from existing approaches, providing a new paradigm for high-quality, automatic entity resolution.
Limitations
- The approach assumes reference tables have low or no duplicates; high duplicate rates can impair safe boundary estimation, reducing precision.
- In highly noisy or highly heterogeneous data, geometric assumptions may break down, leading to decreased accuracy.
- Computational complexity increases with dataset size and configuration space, requiring optimization for large-scale deployment.
Future Work
Future directions include integrating deep feature representations to handle complex data variations, developing active learning strategies to refine parameter inference with minimal supervision, and extending the framework to multi-column and multi-modal data. Improving computational efficiency and scalability for real-time applications is also a priority. Additionally, exploring adaptive distance functions and hybrid models combining geometric and learned features could further enhance robustness and applicability.
AI Executive Summary
Fuzzy-join techniques are vital for entity resolution and data integration but are hampered by complex parameter tuning. Traditional methods rely heavily on manual trial-and-error or supervised learning, which are costly and less scalable. This paper introduces Auto-FuzzyJoin, an innovative framework that automates parameter inference through a geometric interpretation of distance functions. By analyzing the structure of reference tables, which typically have low duplicates, the method estimates safe matching boundaries and learns negative rules to prevent false positives. It combines multiple configurations in a disjunctive manner, maximizing recall while maintaining a target precision. Extensive experiments on 50 Wikipedia datasets demonstrate that Auto-FuzzyJoin outperforms existing unsupervised approaches, achieving an average recall of 85% and approaching the performance of semi-supervised models. This approach significantly reduces the manual effort involved in fuzzy-join parameter tuning, making entity resolution more accessible and reliable. Its interpretability and robustness open new avenues for automated data cleaning, knowledge graph construction, and large-scale data integration. Despite its strengths, the method faces challenges when reference tables contain many duplicates or in highly noisy environments, which could affect accuracy. Future work aims to incorporate deep learning features, optimize scalability, and extend to multi-modal data, promising a broader impact across data science and AI applications.
Deep Analysis
Background
Entity resolution和数据融合在信息系统中扮演核心角色。早期方法多依赖规则或特征工程，效果有限。近年来，基于机器学习的模型如Magellan和DeepMatcher引入深度特征学习，但需大量标注，成本高。模糊匹配技术如Jaccard、Edit距离等已广泛应用，但参数调优依赖经验，难以自动化。随着大数据发展，匹配效率和质量成为瓶颈，促使研究转向无监督和自动参数调节。现有方法虽取得一定进展，但调参繁琐、鲁棒性不足，亟需创新解决方案。
Core Problem
核心问题在于如何在无标注的情况下，自动推断模糊匹配参数以保证高质量匹配。传统方法依赖手工调试，费时费力，且难以适应不同数据特性。参数空间庞大，涉及距离函数、阈值、预处理等多个维度，调优复杂。缺乏理论指导，导致调参过程缺乏可解释性。如何利用参考表的低重复特性，推断安全边界和负规则，成为关键。解决该问题将极大降低实体解析门槛，推动自动化数据整合。
Innovation
本研究的创新点包括：1）提出基于距离空间几何解释的无监督参数推断框架，利用参考表低重复特性自动推导安全边界；2）引入负规则学习机制，自动识别和避免假阳性匹配；3）采用多配置联合策略，将不同参数配置的匹配结果合并，提升召回。与传统方法多依赖启发式或监督不同，该框架无需标注数据，具有良好的可解释性和扩展性。几何距离的自适应调节，有效平衡精度和召回，显著提升匹配效果。该方法为实体解析提供新思路，突破参数调优瓶颈。
Methodology
- �� 以距离函数的几何空间解释为基础，定义安全边界和负规则。• 利用参考表低重复特性，推断哪些距离阈值是“安全”的，即保证高精度。• 通过学习负规则，自动避免误匹配。• 设计多配置联合策略，将不同参数配置的匹配结果合并，提升召回。• 采用无监督优化目标，最大化召回同时满足预设精度。• 利用距离空间的局部结构，动态调整参数，适应不同数据特性。• 在实验中结合几何距离和负规则学习，自动生成匹配程序，避免繁琐调参。
Experiments
采用Wikipedia数据集的50个模糊匹配任务，比较Auto-FuzzyJoin与Magellan、DeepMatcher等半监督模型。指标包括精度、召回率和F1值。设置不同的精度目标（如0.9），评估召回变化。通过不同参数配置的消融实验，验证几何距离推断和负规则学习的贡献。实验还测试在噪声和异构数据下的鲁棒性。结果显示，Auto-FuzzyJoin在保持高精度的同时，召回率提升20%以上，表现出优异的适应性和稳定性。
Results
在Wikipedia任务中，Auto-FuzzyJoin平均召回率达85%，比传统无监督方法高出20%，且在精度目标为0.9时，保持较高召回。几何距离推断有效避免了过度匹配，负规则学习显著减少假阳性。多配置联合策略提升了匹配覆盖范围，整体性能优于现有技术。实验还表明，该方法对数据噪声和异构性具有较强鲁棒性，适应不同场景。
Applications
该技术适用于大规模实体解析、数据整合、知识图谱构建等场景。只需提供参考表和待匹配表，即可自动生成匹配程序，减少人工调参成本。特别适合企业数据仓库、公共数据平台的自动化处理。未来，结合深度特征和多模态信息，将拓展到更复杂的异构数据环境，推动自动化数据治理。
Limitations & Outlook
在参考表存在大量重复或缺失时，安全边界推断可能失效，影响匹配效果。高噪声和极端异构数据场景下，几何距离假设不足，导致性能下降。算法在大规模数据集上计算成本较高，需优化效率。此外，当前模型主要针对单列匹配，扩展到多列匹配仍需研究。未来需解决这些局限，提升算法的适应性和效率。
Plain Language Accessible to non-experts
想象你在整理一堆不同的书籍，要找到相同的书，但每本书的名字都写得不一样，有的拼写错了，有的名字不完整。传统方法就像你用手一一比对，每次都试不同的匹配规则，费时又容易出错。而Auto-FuzzyJoin就像有个聪明的助手，他会观察你的书架，发现哪些书看起来很像，甚至能自动学习哪些拼写错误或不同的名字其实是同一本书。它不用你告诉它具体怎么做，只需要给它一份参考书单，它就能自己推断出哪些书可以匹配，哪些不能。这样，你就不用费力调参数，也能快速找到所有相似的书。这就像有个智能的“书籍匹配专家”，帮你省时省力，还能保证匹配的准确性。
ELI14 Explained like you're 14
想象你在学校图书馆里找书。有时候书名写得不一样，比如有人写“Harry Potter”，有人写“Herry Poter”，还可能有拼写错误。你想找到所有相同的书，但每次都要自己猜哪个拼写对，哪个错，挺麻烦的。Auto-FuzzyJoin就像一个聪明的朋友，他可以看出这些书名其实是一样的，只是写法不同。他不用你告诉他怎么做，只要给他一份正确的书单，他就能学会如何自动匹配那些拼写不同但内容一样的书。这样，你就不用自己试来试去了，朋友帮你搞定了！它用一种特殊的“距离”方法，衡量两个名字有多像，然后自动决定哪些是一样的。就像你用心去找相似的名字，他帮你省了好多时间，还很准。未来，这个方法还能帮你在网上找到相似的图片或视频，变得更聪明、更厉害！
Abstract
Fuzzy similarity join is an important database operator widely used in practice. So far the research community has focused exclusively on optimizing fuzzy join \textit{scalability}. However, practitioners today also struggle to optimize fuzzy-join \textit{quality}, because they face a daunting space of parameters (e.g., distance-functions, distance-thresholds, tokenization-options, etc.), and often have to resort to a manual trial-and-error approach to program these parameters in order to optimize fuzzy-join quality. This key challenge of automatically generating high-quality fuzzy-join programs has received surprisingly little attention thus far. In this work, we study the problem of "auto-program" fuzzy-joins. Leveraging a geometric interpretation of distance-functions, we develop an unsupervised \textsc{Auto-FuzzyJoin} framework that can infer suitable fuzzy-join programs on given input tables, without requiring explicit human input such as labeled training data. Using \textsc{Auto-FuzzyJoin}, users only need to provide two input tables $L$ and $R$, and a desired precision target $τ$ (say 0.9). \textsc{Auto-FuzzyJoin} leverages the fact that one of the input is a reference table to automatically program fuzzy-joins that meet the precision target $τ$ in expectation, while maximizing fuzzy-join recall (defined as the number of correctly joined records). Experiments on both existing benchmarks and a new benchmark with 50 fuzzy-join tasks created from Wikipedia data suggest that the proposed \textsc{Auto-FuzzyJoin} significantly outperforms existing unsupervised approaches, and is surprisingly competitive even against supervised approaches (e.g., Magellan and DeepMatcher) when 50\% of ground-truth labels are used as training data.