2026-08-06T07:52:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8605 2024-03-06T10:42:28Z ddc:004 open_access

Massively Parallel Entity Matching with Linear Classification in Low Dimensional Space Tao, Yufei Entity Matching Linear Programming Range Counting Dominance Join Massively Parallel Computation In entity matching classification, we are given two sets R and S of objects where whether r and s form a match is known for each pair (r, s) in R x S. If R and S are subsets of domains D(R) and D(S) respectively, the goal is to discover a classifier function f: D(R) x D(S) -> {0, 1} from a certain class satisfying the property that, for every (r, s) in R x S, f(r, s) = 1 if and only if r and s are a match. Past research is accustomed to running a learning algorithm directly on all the labeled (i.e., match or not) pairs in R times S. This, however, suffers from the drawback that even reading through the input incurs a quadratic cost. We pursue a direction towards removing the quadratic barrier. Denote by T the set of matching pairs in R times S. We propose to accept R, S, and T as the input, and aim to solve the problem with cost proportional to |R|+|S|+|T|, thereby achieving a large performance gain in the (typical) scenario where |T|<<|R||S|. This paper provides evidence on the feasibility of the new direction, by showing how to accomplish the aforementioned purpose for entity matching with linear classification, where a classifier is a linear multi-dimensional plane separating the matching and non-matching pairs. We actually do so in the MPC model, echoing the trend of deploying massively parallel computing systems for large-scale learning. As a side product, we obtain new MPC algorithms for three geometric problems: linear programming, batched range counting, and dominance join. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yufei Tao 2018 Is Part Of LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2018.20 urn:nbn:de:0030-drops-86057 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.20 eng https://creativecommons.org/licenses/by/3.0/legalcode