Abstract:

Given two sets of entities X and Y, entity matching aims to decide whether x and y represent the same entity for each x in R and y in Y. As the last resort, human experts can be called upon to inspect every (x, y), but this is expensive because the correct verdict could not be determined without investigation efforts dedicated specifically to the two entities x and y involved. It is therefore important to design an algorithm that asks humans to look at only some pairs, and renders the verdicts on the other pairs automatically with good accuracy.

We describe algorithms with non-trivial guarantees on this problem with an active monotone classification approach. We also prove lower bounds that establish the asymptotic optimality of our solutions for a wide range of parameters.

 

Short Bio:

Yufei Tao is a Professor in the Department of Computer Science and Engineering, Chinese University of Hong Kong. He is an ACM distinguished scientist. He received the best-paper award at PODS 2018, and the best-paper awards at SIGMOD in 2013 and 2015, respectively. He was a PC co-chair of ICDE 2014, and will serve as the PC chair of PODS 2020. He served as an associate editor for ACM TODS from 2008 to 2015, and for IEEE TKDE from 2012 to 2014.