Search

International audience; Entity resolution is the task of identifying duplicate entities in a dataset or multiple datasets. In the era of Big Data, this task has gained notorious attention due to the intrinsic quadratic complexity of the problem in relation to the size of the dataset. In practice, this task can be outsourced to a cloud service, and thus, a service customer may be interested in estimating the costs of an entity resolution solution before executing it. Since the execution time of an entity resolution solution depends on a combination of various algorithms, their respective parameter values and the employed cloud infrastructure, in practice it is hard to perform an a priori estimation of infrastructure costs for executing an entity resolution task. Besides estimating customer costs, the estimation of entity resolution costs is also important to evaluate if a set of ER parameter values can be employed to execute a task that meets predefined time and budget restrictions. Aiming to tackle these challenges, we formalize the problem of estimating ER costs taking into account the main parameters that may influence the execution time of the ER task. We also propose an algorithm, denominated T BF , for evaluating the feasibility of ER parameter values, given a set of predefined customer restrictions. Since the efficacy of the proposed algorithm is strongly tied to the accuracy provided by the theoretical estimations of the ER costs, we also present a number of guidelines that can be further explored to improve even more the efficacy of the proposed model.

Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-05-02T21:20:23Z No. of bitstreams: 1 DIMAS CASSIMIRO DO NASCIMENTO FILHO – TESE (PPGCC) 2017.pdf: 1879329 bytes, checksum: bda72914ec66d17611d9d0ab5b9ec6d5 (MD5) Made available in DSpace on 2018-05-02T21:20:23Z (GMT). No. of bitstreams: 1 DIMAS CASSIMIRO DO NASCIMENTO FILHO – TESE (PPGCC) 2017.pdf: 1879329 bytes, checksum: bda72914ec66d17611d9d0ab5b9ec6d5 (MD5) Previous issue date: 2017-11-10 Na era de Big Data, na qual a escala dos dados provê inúmeros desafios para algoritmos clássicos, a tarefa de avaliar a qualidade dos dados pode se tornar custosa e apresentar tempos de execução elevados. Por este motivo, gerentes de negócio podem optar por terceirizar o monitoramento da qualidade de bancos de dados para um serviço específico, usualmente baseado em computação em nuvem. Neste contexto, este trabalho propõe abordagens para redução de custos da tarefa de deduplicação de dados, a qual visa detectar entidades duplicadas em bases de dados, no contexto de um serviço de qualidade de dados em nuvem. O trabalho tem como foco a tarefa de deduplicação de dados devido a sua importância em diversos contextos e sua elevada complexidade. É proposta a arquitetura em alto nível de um serviço de monitoramento de qualidade de dados que emprega o provisionamento dinâmico de recursos computacionais por meio da utilização de heurísticas e técnicas de aprendizado de máquina. Além disso, são propostas abordagens para a adoção de algoritmos incrementais de deduplicação de dados e controle do tamanho de blocos gerados na etapa de indexação do problema investigado. Foram conduzidos quatro experimentos diferentes visando avaliar a eficácia dos algoritmos de provisionamento de recursos propostos e das heurísticas empregadas no contexto de algoritmos incrementais de deduplicação de dados e de controle de tamanho dos blocos. Os resultados dos experimentos apresentam uma gama de opções englobando diferentes relações de custo e benefício, envolvendo principalmente: custo de infraestrutura do serviço e quantidade de violações de SLA ao longo do tempo. Outrossim, a avaliação empírica das heurísticas propostas para o problema de deduplicação incremental de dados também apresentou uma série de padrões nos resultados, envolvendo principalmente o tempo de execução das heurísticas e os resultados de eficácia produzidos. Por fim, foram avaliadas diversas heurísticas para controlar o tamanho dos blocos produzidos em uma tarefa de deduplicação de dados, cujos resultados de eficácia são bastante influenciados pelos valores dos parâmetros empregados. Além disso, as heurísticas apresentaram resultados de eficiência que variam significativamente, dependendo da estratégia de poda de blocos adotada. Os resultados dos quatro experimentos conduzidos apresentam suporte para demonstrar que diferentes estratégias (associadas ao provisionamento de recursos computacionais e aos algoritmos de qualidade de dados) adotadas por um serviço de qualidade de dados podem influenciar significativamente nos custos do serviço e, consequentemente, os custos repassados aos usuários do serviço. In the era of Big Data, in which the scale of the data provides many challenges for classical algorithms, the task of assessing the quality of datasets may become costly and complex. For this reason, business managers may opt to outsource the data quality monitoring for a specific cloud service for this purpose. In this context, this work proposes approaches for reducing the costs generated from solutions for the data deduplication problem, which aims to detect duplicate entities in datasets, in the context of a service for data quality monitoring. This work investigates the deduplication task due to its importance in a variety of contexts and its high complexity. We propose a high-level architecture of a service for data quality monitoring, which employs provisioning algorithms that use heuristics and machine learning techniques. Furthermore, we propose approaches for the adoption of incremental data quality algorithms and heuristics for controlling the size of the blocks produced in the indexing phase of the investigated problem. Four different experiments have been conducted to evaluate the effectiveness of the proposed provisioning algorithms, the heuristics for incremental record linkage and the heuristics to control block sizes for entity resolution. The results of the experiments show a range of options covering different tradeoffs, which involves: infrastructure costs of the service and the amount of SLA violations over time. In turn, the empirical evaluation of the proposed heuristics for incremental record linkage also presented a number of patterns in the results, which involves tradeoffs between the runtime of the heuristics and the obtained efficacy results. Lastly, the evaluation of the heuristics proposed to control block sizes have presented a large number of tradeoffs regarding execution time, amount of pruning approaches and the obtained efficacy results. Besides, the efficiency results of these heuristics may vary significantly, depending of the adopted pruning strategy. The results from the conducted experiments support the fact that different approaches (associated with cloud computing provisioning and the employed data quality algorithms) adopted by a data quality service may produce significant influence over the generated service costs, and thus, the final costs forwarded to the service customers.