Sage Journals: Discover world-class research

Abstract

Entity Resolution (ER) is the method of resolving two similar entities used in the process of data cleaning and data integration. However, existing ER Framework lead to exhaustive pairwise comparisons. The most efficient ER method is blocking, inherently uses exponential pair-wise comparisons for the large databases, leading to poor efficiency in resolving the entities. The real world data can either be homogeneous or heterogeneous, generally of two forms, clean-clean ER which does not have any duplicates or dirty-ER which have duplicates within the dataset. Entity Resolution framework is associated with two phases namely the block building phase which construct the blocks where the similar entities are grouped into a single block for effective indexing, while the aim of block processing phase is to reduce the number of redundant pair-wise comparisons. Another perspective is handling of the entity associated with heterogeneous data, in the proposed work the block building phase aims to gather related entities with different representations into a single block with an approximation space. For this purpose semantic-dominance rough set has been used to cluster the attributes of related entities having a varied schema. The similarity between the entities associated with the clustered attributes is determined using a rough-Jaccard similarity measure, grouped to form blocks of varied, but limited size. The pair-wise comparisons between the blocks of entities are carried out only when the lower approximation of the blocks are same, determined by the proposed multi-criteria Pareto optimality, else the entities are not compared, which signifies, the overall number of pair-wise comparisons is reduced. A performance analysis of the proposed technique has been tested on four real-world, highly heterogeneous datasets, and the validation of these algorithms has yielded 99.98% effectiveness and 98.3% efficiency in block comparison when compared to token blocking and attribute clustering methods.

Keywords

Entity resolution blocking rough set heterogeneous data linked open data

Get full access to this article

View all access options for this article.

References

Fellegi

I.P.

and Sunter

A.B.

, A theory for record linkage, Journal of the American Statistical Association 64(328) (1969), 1183–1210.

Christen

, A survey of indexing techniques for scalable record linkage and deduplication, IEEE Trans Knowl Data Eng 24(9) (2012), 1537–1555.

Bilenko

, Kamath

and Mooney

R.J.

, Adaptive blocking: Learning to scale up record linkage, In ICDM (2006), 87–96.

Bahmani

, Geol

and Sindhe

, Efficient distributed locality sensitive hashing, In CIKM (2012), 2174–2178.

De Vries

, et al., Robust record linkage blocking using suffix arrays, Proceedings of the 18th ACM Conference on Information and Knowledge Management ACM (2009).

Hassanzadeh

, Kementsietsidis

, Lim

, Miller

R.J.

and Wang

, A Framework For Semantic Link Discovery Over Relational Data, In Proceedings of the 18th ACM Conference on Information and Knowledge Management, 2009, pp. 1027–1036. ACM.

Aizawa

A.N.

and Oyama

, A fast linkage detection scheme for multi-source information integration, In WIRI (2005), pp. 30–39.

Saxena

, Gavel

L.K.

, Shrivas

M.M.

, Rough sets for feature selection and classification: An overview with applications, 2014.

Hernández

M.A.

and Stolfo

S.J.

, Real-world data is Dirty: Data cleansing and the merge/purge problem, Data Mining and Knowledge Discovery 2(1) (1998), 9–37.

10.

Volz

, et al., Discovering and maintaining links on the web of data. International Semantic Web Conference, Springer Berlin Heidelberg, 2009.

11.

Whang

S.E.

, et al., Entity resolution with iterative blocking, Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, ACM, 2009.

12.

Bayardo

R.J.

, Ma

and Srikant

, Scaling up all pairs similarity search, Proceedings of the 16th International Conference on World Wide Web ACM, 2007.

13.

Zhang

, et al., A similarity-oriented RDF graph matching algorithm for ranking linked data, Computer and Information Technology (CIT), 2012 IEEE 12th International Conference on, IEEE, 2012.

14.

Gravano

, Ipeirotis

P.G.

, Jagadish

H.V.

, Koudas

, Muthukrishnan

and Srivastava

, Approximate string joins in a database (almost) for free, In VLDB 1 (2001), 491–500.

15.

Leskovec

, Rajaraman

and Ullman

J.D.

, Mining of massive datasets, Cambridge University Press, 2014.

16.

Papadakis

, et al., Meta-blocking: Taking entity resolution to the next level, IEEE Transactions on Knowledge and Data Engineering 26(8) (2014), 1946–1960.

17.

George

, et al., Schema-agnostic vs schema-based configurations for blocking methods on homogeneous data, Proceedings of the VLDB Endowment 9(4) (2015), 312–323.

18.

Papadakis

, et al., Scaling entity resolution to large, heterogeneous data with enhanced meta-blocking, EDBT (2016).

19.

Papadakis

, Papastefanatos

and Palpanas

, Boosting the efficiency of large-scale entity resolution with enhanced meta-blocking, Institute for the Management of Information Systems (2015).

20.

McNeil

, Kardes

and Borthwick

, Dynamic record blocking: Efficient linking of massive databases in MapReduce, In Proceedings of the 10th International Workshop on Quality in Databases (QDB), 2012.

21.

Papadakis

, et al., Efficient entity resolution for large heterogeneous information spaces, Proceedings of the Fourth ACM International Conference on Web Search and Data Mining ACM, 2011.

22.

Papadakis

, et al., Comparative analysis of approximate blocking techniques for entity resolution, Proceedings of the VLDB Endowment 9(9) (2016), 684–695.

23.

Araujo

, et al., SERIMI: Class-based Disambiguation for Effective Instance Matching over Heterogeneous Web Data, WebDB (2012).

24.

Zhang

, et al., A similarity-oriented RDF graph matching algorithm for ranking linked data, Computer and Information Technology (CIT), 2012 IEEE 12th International Conference on IEEE, 2012.

25.

Kolb

, Thor

and Rahm

, Multi-pass sorted neighborhood blocking with MapReduce, Computer Science-Research and Development 27(1) (2012), 45–63.

26.

Kolb

, Thor

and Rahm

, Dedoop: Efficient deduplication with Hadoop, Proceedings of the VLDB Endowment 5(12) (2012), 1878–1881.

27.

Fisher

, Christen

, Wang

and Rahm

, A Clustering-Based Framework to Control Block Sizes for Entity Resolution, KDD’15, Sydney, NSW, Australia, 2015.

28.

Vidhya

K.A.

, Geetha

T.V.

and Aghila

, Text document classification using rough set theory and multi-level naïve bayes, International Journal of Applied Engineering Research (IJAER) 10(75) (2015), 331–336.

29.

Vidhya

K.A.

and Aghila

, Text mining process, techniques and tools: An overview, International Journal of Information Technology and Knowledge Management 2(2) (2010), 613–622.

30.

Vidhya

K.A.

and Aghila

, Hybrid text mining model for document classification, In Computer and Automation Engineering (ICCAE), 2010 The 2nd International Conference on, Vol. 1, 2010, pp. 210–214. IEEE.

31.

Papadakis

, Papastefanatos

, Palpanas

and Koubarakis

, Scaling Entity Resolution to Large, Heterogeneous Data with Enhanced Meta-blocking, International Conference on Extending Database Technology (EDBT), Bordeaux, France: ISBN 978-3-89318-070-7, 2016. on OpenProceedings.org.

32.

Lee

, Lee

and Hwang

S.-W.

, Efficient entity matching using materialized lists, Information Sciences 261 (2014), 170–184, Information Sciences.

33.

Elmagarmid

, Ipeirotis

and Verykios

, Duplicate record detection: A survey, TKDE 19(1) (2007), 1–16.

34.

Kim

and Lee

, HARRA: Fast iterative hashed record linkage for large-scale data collections, In EDBT (2010), 525–536.

35.

Kenig

and Gal

36.

Whang

S.E.

, Marmaros

and Garcia-Molina

, Pay-as-you-go entity resolution, IEEE Transactions on Knowledge and Data Engineering 25(5) (2013), 1111–1124.

37.

Wang

, Cui

and Liang

, Semantic-aware blocking for entity resolution, IEEE Transactions on Knowledge and Data Engineering 28(1) (2016), 166–180.

38.

Vidhya

K.A.

and Geetha

T.V.

, Rough set theory for document clustering: A review, Journal of Intelligent & Fuzzy Systems 32(3) (2017), 2165–2185.

39.

Pawlak

, Rough set theory and its applications to data analysis, Cybernetics & Systems 29(7) (1998), 661–688.

40.

Yadav

and Chatterjee

, A novel approach for feature selection using Rough Sets, Computer, Communications and Electronics (Comptelix), 2017 International Conference on IEEE, 2017.

41.

Qin

and Jing

, The Attribute Reductions Based on Indiscernibility and Discernibility Relations, In International Joint Conference on Rough Sets, Cham, Springer, 2017, pp. 306–316.

42.

Vidhya

K.A.

and Geetha

T.V.

, Resolving Entity in a Large Scale - Determining Linked Entities and Grouping Similar Attributes Represented in Assorted Terminologies, Distributed and Parallel Databases, 2017. https://doi.org/10.1007/s10619-017-7205-1.

Entity resolution framework using rough set blocking for heterogeneous web of data

Abstract

Keywords

Get full access to this article

References