An Attribute Similarity Adjusting Algorithm Based on Functional Dependency

Abstract

Abstract:

Abstract： The accuracy of attribute similarity is one of the important factors affecting the precision of entity resolution (ER). To improve the accuracy of attribute similarity, the relation between attribute similarity and functional dependency (FD) was analyzed and the principles for attribute similarity adjusting were suggested. The FD based methods for similarity partition, similarity transitively adjusting and cost computing of similarity adjusting were proposed. An algorithm for attribute similarity adjusting with FD (SAWFD) was put forward to improve the accuracy of attribute similarity. The experiment results show that the algorithm can better distinguish matching and unmatching records, and get higher scores of recall, precision and F1 measure.

Key words: entity resolution, attribute similarity, functional dependencies

CLC Number:

TP 311

TAN Mingchaoa,DIAO Xingchuna,CAO Jianjuna,FENG Jingb. An Attribute Similarity Adjusting Algorithm Based on Functional Dependency[J]. Journal of Shanghai Jiaotong University, 2015, 49(08): 1075-1083.

References

［1］Papadakis G, Ioannou E, Niederée C, et al. Eliminating the redundancy in blockingbased entity resolution methods［C］∥ Glen Newton. Proceedings of the 11th annual international ACM/IEEE joint conference on Digital libraries. Ottawa：ACM，2011：8594.

［2］Papadakis G, Ioannou E, Niederée C, et al. Efficient entity resolution for large heterogeneous information spaces［C］∥ Irwin King. Proceedings of the fourth ACM international conference on Web search and data mining. Hong Kong：ACM，2011：535544.

［3］Papadakis G, Ioannou E, Niederée C, et al. To compare or not to compare: making entity resolution more efficient［C］∥ Roberto De Virgilio, Fausto Giunchiglia, Letizia Tanca. Proceedings of the International Workshop on Semantic Web Information Management. Athens：ACM，2011：3.

［4］Lange D, Naumann F. Efficient similarity search: arbitrary similarity measures, arbitrary composition［C］∥ Bettina Berendt, Arjen de Vries, Wenfei Fan. Proceedings of the 20th ACM international conference on Information and knowledge management. Glasgow：ACM，2011：16791688.

［5］Heath T, Bizer C. Linked data: Evolving the web into a global data space［J］. Synthesis lectures on the semantic web: theory and technology，2011，1(1)：1136.

［6］Paradies M, Malaika S, Siméon J, et al. Entity matching for semistructured data in the Cloud［C］∥ Sascha Ossowski, Rey Juan Carlos. Proceedings of the 27th Annual ACM Symposium on Applied Computing. Trento：ACM，2012：453458.

［7］Snae C. A comparison and analysis of name matching algorithms［J］. International Journal of Applied Science, Engineering and Technology, 2007，4(1)：252257.

［8］Wang J, Li G, Yu J X, et al. Entity matching: how similar is similar［J］. Proceedings of the VLDB Endowment，2011，4(10)：622633.

［9］Christen P. Data matching: concepts and techniques for record linkage, entity resolution, and duplicate detection［M］. New York：Springer Science & Business Media，2012.

［10］Naumann F, Herschel M. An introduction to duplicate detection［J］. Synthesis Lectures on Data Management，2010，2(1)：187.

［11］Dorneles C F, Gonalves R, Ronaldo dos Santos Mello. Approximate data instance matching: a survey［J］. Knowledge and Information Systems，2011，27(1)：121.

［12］Abril D, NavarroArribas G, Torra V. Improving record linkage with supervised learning for disclosure risk assessment［J］. Information Fusion， 2012，13(4)：274284.

［13］Mannila H, Rih K J. Algorithms for inferring functional dependencies from relations［J］. Data & Knowledge Engineering，1994，12(1)：8399.

［14］Huhtala Y, Krkkinen J, Porkka P, et al. TANE: An efficient algorithm for discovering functional and approximate dependencies［J］. The Computer Journal，1999，42(2)：100111.

［15］张守志，施伯乐. 一种发现函数依赖集的方法及应用［J］. 软件学报，2003，14(10)：16921696.

ZHANG Shouzhi, SHI Bole. A method for discovering functional dependencies and its application［J］. Journal of Software，2003，14(10)：16921696.

［16］Huhtala Y, Karkkainen J, Porkka P, et al. Efficient discovery of functional and approximate dependencies using partitions［C］∥ Proceedings of 14th International Conference on Data Engineering. Orlando：IEEE，1998：392401.

［17］Weis M, Naumann F. Detecting duplicate objects in XML documents［C］∥ Felix Naumann, Monica Scannapieco. Proceedings of the 2004 International Workshop on Information quality in information systems. Paris：ACM，2004：1019.

［18］Benjelloun O, GarciaMolina H, Gong H, et al. Dswoosh: A family of algorithms for generic, distributed entity resolution［C］∥ Proceedings of 27th International Conference on Distributed Computing Systems. Toronto：IEEE，2007：3737.