FIRLA: a Fast Incremental Record Linkage Algorithm
FIRLA: a Fast Incremental Record Linkage Algorithm
复制标题
DOI：
10.1016/j.jbi.2022.104094
复制
发表时间：
2022-05-16
影响因子：
4.5
通讯作者：
Rajasekaran，Sanguthevar
中科院分区：
文献类型：
--
作者：
Soliman，Ahmed;Rajasekaran，Sanguthevar
病历链接是包括生物医学信息学在内的许多领域广泛研究的一个重要问题。这个问题的一个标准版本是对来自多个数据集的记录进行集群，使得每个集群只有与一个人相关的记录。通常，数据集的大小是巨大的。因此，现有的记录链接算法需要很长的时间。因此，开发新的记录链接的快速算法是至关重要的。该问题的增量版本是将先前聚类的记录与添加到输入数据集中的新记录相链接，创建了一种新的算法来高效地执行标准和增量记录链接。该算法利用了一组有效的技术，显著限制了记录对比较和距离计算的数量。我们的算法显示，与最先进的链接问题相比，标准链接问题的平均速度提高了2.4倍(最高可达4倍)，而链接性能没有任何下降。平均而言，我们的算法仅需33%的从头开始链接记录所需的时间就可以增量链接记录，并且在比较属性数大于2的所有情况下，我们的算法都达到了相当或更好的链接性能并且在链接时间方面优于现有技术。在实践中，两个以上的比较属性是相当常见的。该算法是非常有效的，可以用于实际的记录链接应用，特别是当记录随着时间的推移而被添加，并且链接输出需要频繁更新时。
Record linkage is an important problem studied widely in many domains including biomedical informatics. A standard version of this problem is to cluster records from several datasets, such that each cluster has records pertinent to just one individual. Typically, datasets are huge in size. Hence, existing record linkage algorithms take a very long time. It is thus essential to develop novel fast algorithms for record linkage. The incremental version of this problem is to link previously clustered records with new records added to the input datasets.A novel algorithm has been created to efficiently perform standard and incremental record linkage. This algorithm leverages a set of efficient techniques that significantly restrict the number of record pair comparisons and distance computations. Our algorithm shows an average speed-up of 2.4x (up to 4x) for the standard linkage problem as compared to the state-of-the-art, without any drop in linkage performance at all. On average, our algorithm can incrementally link records in just 33% of the time required for linking them from scratch.Our algorithms achieve comparable or superior linkage performance and outperform the state-of-the-art in terms of linking time in all cases where the number of comparison attributes is greater than two. In practice, more than two comparison attributes are quite common. The proposed algorithm is very efficient and could be used in practice for record linkage applications especially when records are being added over time and linkage output needs to be updated frequently.