  Blocking is a mechanism to improve the efficiency of Entity Resolution (ER)
which aims to quickly prune out all non-matching record pairs. However,
depending on the distributions of entity cluster sizes, existing techniques can
be either (a) too aggressive, such that they help scale but can adversely
affect the ER effectiveness, or (b) too permissive, potentially harming ER
efficiency. In this paper, we propose a new methodology of progressive blocking
(pBlocking) to enable both efficient and effective ER, which works seamlessly
across different entity cluster size distributions. pBlocking is based on the
insight that the effectiveness-efficiency trade-off is revealed only when the
output of ER starts to be available. Hence, pBlocking leverages partial ER
output in a feedback loop to refine the blocking result in a data-driven
fashion. Specifically, we bootstrap pBlocking with traditional blocking methods
and progressively improve the building and scoring of blocks until we get the
desired trade-off, leveraging a limited amount of ER results as a guidance at
every round. We formally prove that pBlocking converges efficiently ($O(n log^2
n)$ time complexity, where n is the total number of records). Our experiments
show that incorporating partial ER output in a feedback loop can improve the
efficiency and effectiveness of blocking by 5x and 60% respectively, improving
the overall F-score of the entire ER process up to 60%.
