# A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution

arXiv: https://arxiv.org/abs/1702.01208 · HTML: https://mlsanity.com/paper/1702.01208/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2017.

## Built on by (most cited first, 9 of 9)

- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [Optimal Clustering with Noisy Queries via Multi-Armed Bandit](https://mlsanity.com/paper/2207.05376/) (2022)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Fuzzy Clustering with Similarity Queries](https://mlsanity.com/paper/2106.02212/) (2021)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

Entity resolution (ER) is the task of identifying all records in a database that refer to the same underlying entity, and are therefore duplicates of each other. Due to inherent ambiguity of data representation and poor data quality, ER is a challenging task for any automated process. As a remedy, human-powered ER via crowdsourcing has become popular in recent years. Using crowd to answer queries is costly and time consuming. Furthermore, crowd-answers can often be faulty. Therefore, crowd-based ER methods aim to minimize human participation without sacrificing the quality and use a computer generated similarity matrix actively. While, some of these methods perform well in practice, no theoretical analysis exists for them, and further their worst case performances do not reflect the experimental findings. This creates a disparity in the understanding of the popular heuristics for this problem. In this paper, we make the first attempt to close this gap. We provide a thorough analysis of the prominent heuristic algorithms for crowd-based ER. We justify experimental observations with our analysis and information theoretic lower bounds.