Exploiting block co-occurrence to control block sizes for entity resolution
Tóm tắt
The problem of identifying duplicated entities in a dataset has gained increasing importance during the last decades. Due to the large size of the datasets, this problem can be very costly to be solved due to its intrinsic quadratic complexity. Both researchers and practitioners have developed a variety of techniques aiming to speed up a solution to this problem. One of these techniques is called blocking, an indexing technique that splits the dataset into a set of blocks, such that each block contains entities that share a common property evaluated by a blocking key function. In order to improve the efficacy of the blocking technique, multiple blocking keys may be used, and thus, a set of blocking results is generated. In this paper, we investigate how to control the size of the blocks generated by the use of multiple blocking keys and maintain reasonable quality results, which is measured by the quality of the produced blocks. By controlling the size of the blocks, we can reduce the overall cost of solving an entity resolution problem and facilitate the execution of a variety of tasks (e.g., real-time and privacy-preserving entity resolution). For doing so, we propose many heuristics which exploit the co-occurrence of entities among the generated blocks for pruning, splitting and merging blocks. The experimental results we carry out using four datasets confirm the adequacy of the proposed heuristics for generating block sizes within a predefined range threshold as well as maintaining reasonable blocking quality results.
Tài liệu tham khảo
Batini C, Scannapieco M (2016) Data quality dimensions. Springer, Cham, pp 21–51
Batini C, Cappiello C, Francalanci C, Maurino A (2009) Methodologies for data quality assessment and improvement. ACM Comput Surv (CSUR) 41(3):16
Bilenko M, Kamath B, Mooney RJ (2006) Adaptive blocking: learning to scale up record linkage. In: Sixth international conference on data mining, ICDM’06. IEEE, pp 87–96
Christen P (2012) Data matching: concepts and techniques for record linkage, entity resolution, and duplicate detection. Springer, New York
Christen P (2012) A survey of indexing techniques for scalable record linkage and deduplication. IEEE Trans Knowl Data Eng 24(9):1537–1555
Cohen WW, Richman J (2002) Learning to match and cluster large high-dimensional data sets for data integration. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 475–480
Costa G, Manco G, Ortale R (2010) An incremental clustering scheme for data de-duplication. Data Min Knowl Discov 20(1):152–187
Covell M, Baluja S (2009) Lsh banding for large-scale retrieval with memory and recall constraints. In: IEEE international conference on acoustics, speech and signal processing, ICASSP 2009. IEEE, pp 1865–1868
De Vries T, Ke H, Chawla S, Christen P (2009) Robust record linkage blocking using suffix arrays. In: Proceedings of the 18th ACM conference on Information and knowledge management. ACM, pp 305–314
do Nascimento DC, Pires CES, Mestre DG (2018) Heuristic-based approaches for speeding up incremental record linkage. J Syst Softw 137:335–354
Ebraheem M, Thirumuruganathan S, Joty S, Ouzzani M, Tang N (2018) Distributed representations of tuples for entity resolution. Proc VLDB Endow 11(11):1454–1467
Fisher J, Christen P, Wang Q, Rahm E (2015) A clustering-based framework to control block sizes for entity resolution. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 279–288
Ganganath N, Cheng CT, Chi KT (2014) Data clustering with cluster size constraints using a modified \(k\)-means algorithm. In: 2014 International conference on cyber-enabled distributed computing and knowledge discovery (CyberC). IEEE, pp 158–161
Giraud-Carrier C, Goodliffe J, Jones BM, Cueva S (2015) Effective record linkage for mining campaign contribution data. Knowl Inf Syst 45(2):389–416
Gomes Mestre D, Pires CES (2013) Improving load balancing for mapreduce-based entity matching. In: 2013 IEEE symposium on computers and communications (ISCC). IEEE, pp 000618–000624
Gruenheid A, Dong XL, Srivastava D (2014) Incremental record linkage. Proc VLDB Endow 7(9):697–708
Hassanzadeh O, Chiang F, Lee HC, Miller RJ (2009) Framework for evaluating clustering algorithms in duplicate detection. Proc VLDB Endow 2(1):1282–1293
Kolb L, Thor A, Rahm E (2012) Multi-pass sorted neighborhood blocking with mapreduce. Comput Sci Res Dev 27(1):45–63
Koudas N, Sarawagi S, Srivastava D (2006) Record linkage: similarity measures and algorithms. In: Proceedings of the 2006 ACM SIGMOD international conference on Management of data. ACM, pp 802–803
Malinen MI, Fränti P (2014) Balanced \(k\)-means for clustering. In: Joint IAPR international workshops on statistical techniques in pattern recognition (SPR) and structural and syntactic pattern recognition (SSPR). Springer, pp 32–41
Mann W, Augsten N, Bouros P (2016) An empirical evaluation of set similarity join techniques. Proc VLDB Endow 9(9):636–647
Mestre DG, Pires CE, Nascimento DC (2015) Adaptive sorted neighborhood blocking for entity matching with mapreduce. In: Proceedings of the 30th annual ACM symposium on applied computing. ACM, pp 981–987
Mestre DG, Pires CES, Nascimento DC (2017) Towards the efficient parallelization of multi-pass adaptive blocking for entity matching. J Parallel Distrib Comput 101:27–40
Michelson M, Knoblock CA (2006) Learning blocking schemes for record linkage. In: AAAI, pp 440–445
Nascimento DC, Pires CE, Mestre D (2015) Data quality monitoring of cloud databases based on data quality SLAs. In: Trovati M, Hill R, Anjum A, Zhu S, Liu L (eds) Big-data analytics and cloud computing. Springer, Cham, pp 3–20
Papadakis G, Koutrika G, Palpanas T, Nejdl W (2014) Meta-blocking: taking entity resolutionto the next level. IEEE Trans Knowl Data Eng 26(8):1946–1960
Papadakis G, Papastefanatos G, Koutrika G (2014) Supervised meta-blocking. Proc VLDB Endow 7(14):1929–1940
Papenbrock T, Heise A, Naumann F (2015) Progressive duplicate detection. IEEE Trans Knowl Data Eng 27(5):1316–1329
Ramadan B, Christen P, Liang H, Gayler RW (2015) Dynamic sorted neighborhood indexing for real-time entity resolution. J Data Inf Qual 6(4):15
Ranbaduge T, Vatsalan D, Christen P (2015) Clustering-based scalable indexing for multi-party privacy-preserving record linkage. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 549–561
Ranbaduge T, Vatsalan D, Christen P, Verykios V (2016) Hashing-based distributed multi-party blocking for privacy-preserving record linkage. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 415–427
Rebollo-Monedero D, Solé M, Nin J, Forné J (2013) A modification of the \(k\)-means method for quasi-unsupervised learning. Knowl Based Syst 37:176–185
Vatsalan D, Christen P, Verykios VS (2013) A taxonomy of privacy-preserving record linkage techniques. Inf Syst 38(6):946–969
Vatsalan D, Christen P (2013) Sorted nearest neighborhood clustering for efficient private blocking. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 341–352
Verykios VS, Karakasidis A, Mitrogiannis VK (2009) Privacy preserving record linkage approaches. Int J Data Min Model Manag 1(2):206–221
Whang SE, Menestrina D, Koutrika G, Theobald M, Garcia-Molina H (2009) Entity resolution with iterative blocking. In: Proceedings of the 2009 ACM SIGMOD international conference on management of data. ACM, pp 219–232
Whang SE, Marmaros D, Garcia-Molina H (2013) Pay-as-you-go entity resolution. IEEE Trans Knowl Data Eng 25(5):1111–1124
Yan S, Lee D, Kan MY, Giles LC (2007) Adaptive sorted neighborhood methods for efficient record linkage. In: Proceedings of the 7th ACM/IEEE-CS joint conference on digital libraries. ACM, pp 185–194
Zhu S, Wang D, Li T (2010) Data clustering with size constraints. Knowl Based Syst 23(8):883–889