QUERY-STRUCTURED PRUNING FOR PROGRESSIVE ENTITY RESOLUTION

Abstract

Entity resolution (ER) is the task of determining whether records across different datasets refer to the same real world entity. It is a foundational operation in modern data infrastructure. Organizations encounter ER as a persistent operational concern embedded in Master Data Management systems, procurement pipelines, healthcare record linkage, and financial compliance workflows. Despite decades of research, existing systems are poorly adapted to the organizational realities of these deployments: queries arrive under latency and budget constraints, different downstream tasks demand different resolution strategies applied to the same data, and the full dataset need never be resolved if only a subset of entities is relevant to a given query. BrewER is a progressive, query time entity resolution system designed to address these constraints. Rather than resolving records globally at ETL time, BrewER defers resolution to query time and emits results progressively as they become available, subject to an explicit budget. This thesis asks whether BrewER's algorithmic framework can be improved to reduce the number of matching comparisons required to answer conjunctive HAVING queries, without sacrificing correctness. The contribution is D10, a composition of two query structured pruning mechanisms. The first, Seed Partitioning (D5), operates before resolution begins: it inspects the blocking neighborhood of each candidate seed record and prunes any seed whose neighborhood cannot possibly cover all HAVING clause conditions under AND semantics, eliminating those seeds from the priority queue before any matching function invocations are made. The second, the Phase 2 Gate (D7), operates during resolution: after Phase 1 has produced the initial match cluster for a given seed, it checks whether Phase 2 expansion can possibly produce an entity satisfying the remaining unsatisfied conditions, and skips Phase 2 entirely if not. Both mechanisms are proven sound: no entity that would be emitted by the BrewER baseline is suppressed by D10. Evaluation on two BrewER benchmark datasets which are magellan_beers and nyc_funding_applications. Using 100 queries spanning AND and OR query types shows that D10 reduces total matching comparisons by 31.1% with zero correctness regressions. Savings scale monotonically with conjunct count: 0% for single condition AND queries (a structural guarantee), 72.8% for two condition AND queries, and 80.9% for three condition AND queries. The top K progressive analysis confirms that D10 savings are front loaded, reducing the cost of the first emitted entity most sharply, which is the operationally relevant metric for interactive progressive ER workloads.