Entity Resolution (ER) is the process of identifying and merging records that refer to the same real-world entity. ER is usually applied as an expensive cleaning step on the entire data before consuming it, yet the relevance of cleaned entities ultimately depends on the user's specific application, which may only require a small portion of the entities. We introduce BrewER, a framework designed to evaluate SQL SP queries on unclean data while progressively providing results as if they were obtained from cleaned data. BrewER aims at cleaning a single entity at a time, adhering to an ORDER BY predicate, thus it inherently supports top-k queries and stop-and-resume execution. This approach can save a significant amount of resources for various applications. BrewER has been implemented as an open-source Python library and can be seamlessly employed with existing ER tools and algorithms. We thoroughly demonstrated its eficiency through its evaluation on four real-world datasets.
(a) Offline ER (b) Query Choose a matching function: μ() - μ_customers_DL_Transfer_1 - μ_customers_DL_Transfer_2 ... - μ_electronics_DL_custom_n ... a t a d y itr d new data
Choose resolution functions: α1() = MIN(<customer_id>) α2() = MAX(<data_month_usage>) α3() = AVG(<calls_month>)
Q1 SELECT customer_id FROM customer WHERE data_month_usage > ’10GB’
ORDER BY calls_month DESC Query exec.
ll a c e r Qcomparisons cleaned data cleaned data clean results (c) Query w/ BrewER Q2 SELECT TOP 50
MIN(customer_id),
AVG(calls_month) FROM customer GROUP BY ENTITY WITH MATCHER μ
HAVING MAX(data_month_usage)>’10GB’ new data ORDER BY AVG(calls_month) DESC a t a d y itr d
ll a c e r
Qcomparisons progressive clean results 1.1. Executing queries on dirty data with existing solutions Traditionally, ER is employed as a cleaning step before using the data. Yet, in many practical scenarios this might not be convenient: Example 1.1. Ellen is a data scientist building a machine learning model to predict customer churn for a telecom company, with the following requirements: (i) she has limited time to add new data to her dataset, which will contain duplicates; (ii) she has business priorities: it is better to have clean data for high-value customers (i.e., those that make more phone calls) than for low-value ones, and only customers with a certain data usage (e.g., those that have a monthly data usage greater than 10 GB) should be considered—she can express this with Query 1 in Figure 1b.
For ER, Ellen already has a matching function to choose (adapting some internal pre-trained deep learning models) and she knows rules for resolving the conflicts in the attribute values of the clusters of matching records (e.g., AVG(calls_month), MAX(data_month_usage), etc.).
The example above depicts a common scenario for data practitioners (e.g., data scientists), characterized by: • An information need: only some entities are relevant and some entities are more relevant than others; • Time constraints: data might become outdated quickly and/or users want to do a fast exploration of relevant portions of cleaned data.
Example 1.2. To get correct results for the query (i.e., taking into account that some records are duplicates) Ellen employs a traditional ER framework to clean the entire dataset (Figure 1a). However, she soon realizes that ER is the bottleneck due to its inherently quadratic complexity and the cost of the matching function, which involves expensive operations based on deep neural network models. As a result, it takes a significant amount of time to clean the entire dataset using ER. Furthermore, to build the right ER pipeline is not a trivial task: she would need to debug the ER pipeline with the data at hand (e.g., to check if the matcher she is employing is performing well for high-value customers), but she cannot stop the ER process after receiving a handful of the entities to inspect—this is because those entities might not be relevant for the query or might be only partially resolved, which could lead to incorrect results. Alternatively, she would have to manually select records from the dataset to test the ER pipeline, which is also time-consuming.
The motivating example highlights the need for a more eficient and targeted approach to ER
that prioritizes cleaning.
1.2. A novel approach to execute queries on dirty data
We propose BrewER1 [
[non-match]> matchDB NMaotncMhaLticshtLsi,sts
BrewER
Entity Matching
Blocking
Query progressive cleaned results
ER progressively on the right portion of the data to yield correct results incrementally. This allows Ellen to receive the first entities in a fraction of the time required by existing ER frameworks. She can explore new data without completely cleaning it and maximize the ER eforts on the entities she actually needs for her task. Moreover, BrewER allows Ellen to stop the execution at any time with the guarantee that the results produced so far are correct. She can then inspect the results of the ER process for entities of interest and debug it if needed. This feature saves time and resources compared to traditional ER frameworks, where debugging and testing the ER pipeline requires a complete cleaning of the entire dataset. Finally, BrewER keeps track of both executed comparisons and resolved entities to avoid repeating the same operations when multiple queries are issued on the same data. This further improves the eficiency of the ER process, allowing Ellen to perform her analysis more quickly and accurately.
More generally, our proposed approach is well-suited for addressing one of the major
challenges in data lake management systems [
The main contributions of BrewER can be summarized as follows. We formalize the concept of ER-on-demand, which involves progressively cleaning and emitting entities that satisfy queries issued directly on dirty datasets, and propose an algorithm for it. Finally, we implement this algorithm in an open-source system and extensively evaluate it on four real-world datasets, demonstrating its efectiveness.
BrewER is designed as a flexible and adaptable framework, as illustrated in Figure 2. It is
implemented as a Python library, whose code is publicly available on GitHub2. This approach
allows the seamless integration of BrewER into Python workflows in Jupyter3 notebooks,
as we show below in Section 3. Being BrewER agnostic towards the selected blocking and
matching functions, users can integrate it with their preferred binary matching libraries (such
as DeepMatcher [
SELECT [TOP ] ⟨ ()⟩
FROM [WHERE ] GROUP BY ENTITY WITH MATCHER
[HAVING ⟨ () {LIKE|IN|<|≤ |>|≥ |=} ⟩]
[ORDER BY () [ASC|DESC]]
or SparkER [
In particular, BrewER builds on the output of the blocking function and performs a preliminary ifltering of the blocks, keeping only the ones containing records whose values might lead to the generation of an entity appearing in the result of the query. The records of the blocks that pass the filtering are then inserted in a priority queue, keeping for each one the list of its candidate matches. The priority is defined according to the value of the attribute appearing in the ORDER BY clause, in ascending or descending order. BrewER iterates on the priority queue, considering at each iteration the head element: if it is a record, its candidate matches are checked generating a completely resolved entity; otherwise (i.e., it is a completely resolved entity), it is emitted or discarded based on whether or not it satisfies the query.
To optimize the performance of the matching functions and avoid re-comparing candidate pairs, BrewER maintains separate databases for the lists of matching and non-matching records for each matching function adopted by the user. To save space, users may opt to store only the ifnal resolved entities—the resolution functions cannot change across queries in this case. 2.1. Supported queries
Through our experimental evaluation [
In Figure 4, we show the results obtained by running batches of conjunctive (i.e., with the
HAVING conditions in AND) and disjunctive (i.e., with the HAVING conditions in OR) queries
with BrewER on the four datasets. The plot shows the average number of comparisons needed
to reach a certain query recall (i.e., the emission of a certain percentage of resulting entities).
BrewER is able to return the entities with a high priority in a small fraction of the time
required for performing the entire cleaning process, which has to be carried out by the batch
algorithms to get the query results (here we consider as a baseline QDA [
The shortcomings of the traditional batch approach to ER are pointed out in literature and
diferent solutions have been proposed to overcome its limitations in dynamic scenarios. In
particular, the related work can be grouped into two main research directions: progressive
approaches and query-driven approaches. These methods present several significant diferences
compared to BrewER [
We presented BrewER [