Parallel Discrepancy Detection and Incremental Detection

CategoryPublications Publications 327

Authors: Wenfei Fan,Chao Tian, Yanghao Wang, Qiang Yin

Name of Conference: International Conference on Very Large Data Bases (VLDB 2021), Aug 16- 20, 2021, Copenhagen, Denmark

Date of Publication: Apr, 2021


This paper studies how to catch duplicates, mismatches and conflicts in the same process. We adopt a class of entity enhancing rules that embed machine learning predicates, unify entity resolution and conflict resolution, and are collectively defined across multiple relations. We detect discrepancies as violations of such rules. We establish the complexity of discrepancy detection and incremental detection problems with the rules; they are both NP-complete and W[1]-hard. To cope with the intractability and scale with large datasets, we develop parallel algorithms and parallel incremental algorithms for discrepancy detection. We show that both algorithms are parallelly scalable, i.e., they guarantee to reduce runtime when more processors are used. Moreover, the parallel incremental algorithm is relatively bounded. The complexity bounds and algorithms carry over to denial constraints, a special case of the entity enhancing rules. Using real-life and synthetic datasets, we experimentally verify the effectiveness, scalability and efficiency of the algorithms.

View Full Text

Keywords2021VLDBWenfei Fan Previous: Next: