Deduplicação em Grande Escala com Restrições Usando Dedupalog

Apresentamos uma estrutura declarativa para a deduplicação coletiva de referências de entidades na presença de restrições. Restrições ocorrem naturalmente em muitos domínios de limpeza de dados e podem melhorar a qualidade da deduplicação. Um exemplo de uma restrição é "cada artigo tem um local de publicação único"; se duas referências de artigos forem duplicadas, então suas referências de conferências associadas também devem ser duplicadas. Nossa estrutura suporta deduplicação coletiva, significando que podemos deduplicar tanto referências de artigos quanto referências de conferências coletivamente no exemplo acima. Nossa estrutura é baseada em uma linguagem simples no estilo Datalog com semântica precisa. A maioria dos trabalhos anteriores sobre deduplicação ou ignora restrições ou as usa de maneira ad-hoc específica de domínio. Também apresentamos algoritmos eficientes para suportar a estrutura. Nossos algoritmos têm garantias teóricas precisas para uma grande subclasse de nossa estrutura. Mostramos, usando uma implementação protótipo, que nossos algoritmos escalam para conjuntos de dados muito grandes. Fornecemos resultados experimentais detalhados sobre dados do mundo real demonstrando a utilidade de nossa estrutura para deduplicação de alta qualidade e escalável.