Introduction
Author Name Disambiguation (AND) is a critical task in scholarly database management, aimed at determining whether multiple mentions of a name (e.g., "J. Smith" and "John Smith") refer to the same individual. In massive datasets like PubMed, which contains over 80 million author mentions, a naive $O(n^2)$ comparison approach is computationally infeasible. To address this, researchers employ blocking, a technique that filters out unlikely candidate pairs to reduce the search space. This paper proposes a novel blocking method using Conjunctive Normal Form (CNF) to achieve high efficiency and scalability without sacrificing accuracy.
Methodology
The core of the proposed approach is learning blocking schemes expressed in CNF—a series of "AND" requirements where each requirement is a set of "OR" options. For example, a rule might require a [Last Name Match] AND [First Initial Match OR Co-author Match].
Logical Duality and Early Rejection
The authors leverage the logical duality between CNF and the more common Disjunctive Normal Form (DNF). While DNF focuses on covering all positive matches, CNF is optimized for filtering out negative matches. Because a CNF formula is a sequence of conjunctions, the system can implement "early rejection": as soon as a single clause fails, the pair is discarded, significantly reducing processing time.
Disjoint Blocking for Parallelization
To handle the scale of 80 million records, the authors developed a disjoint blocking strategy. This ensures that each record is assigned to exactly one block, making the subsequent clustering steps "embarrassingly parallel." This allows the workload to be distributed across multiple CPU threads without inter-process communication overhead.
Experimental Setup
The method was evaluated using two datasets:
- PubMed Benchmark: A manually verified subset of 214 unique authors and 3,964 mentions, used for training and cross-validation.
- Full PubMed Database: A 2016 snapshot containing 80 million author mentions across 24 million publications.
Results and Discussion
The CNF blocking approach demonstrated superior performance compared to traditional methods. On the benchmark dataset, CNF achieved a Reduction Ratio (RR) of 0.882 at a Pairs Completeness (PC) of 0.99, significantly outperforming DNF-based blocking.
The system's scalability was proven by processing the entire PubMed database in just 10.5 minutes using 24 threads. During this run, it successfully filtered out 82.17% of all possible author pairs.
The authors also compared the performance of disjoint versus nondisjoint CNF variants. While disjoint blocking is necessary for optimal parallelization, the results indicate it is slightly more restrictive than nondisjoint blocking, which offers a higher reduction ratio at high completeness levels.
Conclusion
By focusing on efficient rejection through CNF and enabling massive parallelization via disjoint blocks, this work provides a scalable solution for author name disambiguation at the scale of tens of millions of records. Future work will explore multi-level blocking strategies and mathematical optimization of CNF formulas using linear programming.
Summary updated