FIRLA: a Fast Incremental Record Linkage Algorithm.

Area of Science:

• Biomedical informatics
• Data science
• Computer science

Background:

• Record linkage is crucial for data integration, particularly in biomedical informatics, but existing methods are slow on large datasets.
• The incremental version of record linkage, updating clusters with new data, presents unique computational challenges.
• Developing faster algorithms is essential for practical application of record linkage on massive datasets.

Purpose of the Study:

• To develop a novel, efficient algorithm for both standard and incremental record linkage.
• To significantly reduce the computational time required for record linkage without compromising accuracy.
• To address the limitations of existing algorithms in handling large-scale datasets and frequent data updates.

Main Methods:

• The algorithm employs efficient techniques to minimize record pair comparisons and distance calculations.
• It is designed to handle both the initial (standard) record linkage and the ongoing (incremental) updates.
• Performance was evaluated against state-of-the-art methods on standard and incremental linkage tasks.

Main Results:

• Achieved an average speed-up of 2.4x (up to 4x) for standard record linkage compared to existing methods, with no loss in accuracy.
• Incrementally linked records in approximately 33% of the time required for linking from scratch.
• Outperformed state-of-the-art methods in linking time for datasets with more than two comparison attributes, achieving comparable or superior linkage performance.

Conclusions:

• The novel algorithm offers significant speed improvements for standard and incremental record linkage.
• Its efficiency makes it suitable for practical applications, especially those requiring frequent updates.
• The method provides a viable solution for large-scale data integration challenges in various domains.