Keyword-search systems for databases aim to answer a user query composed of a few terms with a ranked list of records. They are powerful and easy-to-use data exploration tools for a wide range of contexts. For instance, given a product database gathered scraping e-commerce websites, these systems enable even non-technical users to explore the item set (e.g., to check whether it contains certain products or not, or to discover the price of an item). However, if the database contains dirty records (i.e., incomplete and duplicated records), a preprocessing step to clean the data is required. One fundamental data cleaning step is Entity Resolution, i.e., the task of identifying and fusing together all the records that refer to the same real-word entity. This task is typically executed on the whole data, independently of: (i) the portion of the entities that a user may indicate through keywords, and (ii) the order priority that a user might express through an order by clause. This paper describes a rst step to solve the problem of progressive search-driven Entity Resolution: resolving all the entities described by a user through a handful of keywords, progressively (according to an order by clause). We discuss the features of our method, named SearchER and showcase some examples of keyword queries on two real-world datasets obtained with a demonstrative prototype that we have built.
Entity Resolution (ER) is a fundamental task for data cleaning and
integration [
When the computational resources and/or the time are critical components for
ER [
Employing a traditional batch approach to ER, i.e., resolving the whole dataset and then executing the query, might be quite expensive on real datasets composed of millions of entities. Even existing progressive ER approaches are useless with such a problem, since they aim to approximate the optimal order of the record comparisons on the basis of the matching likelihood of the record pairs|the matching likelihood is assessed through heuristics, such as the similarity of some attributes. Thus, to generate the nal result for Query 1, they have to perform the whole ER process; this is because the most expensive Apple iPhone 8 entity might correspond to records that have the lowest matching likelihood in the dataset.
In this paper, we investigate the problem of the progressive search-driven Entity Resolution. We propose a rst attempt to address this problem by envisioning an ER method, called SearchER, which enables users to express the relevance of the entities of their interest by means of a keyword query combined with the selection of an attribute that determines the ordering (descending or ascending).
From the user point of view, SearchER takes as input: (i) a dirty dataset, (ii) a blocking function, (iii) a user keyword query (which de nes the entities of interest), (iv) an attribute for the ordering predicate, and (v) the ordering type (i.e., ascending or descending ). Then, SearchER returns as output the solution for the user query, progressively. Under the hood SearchER exploits the blocking function to de ne the space of possible comparisons; then it identi es some initial candidate records to be resolved (i.e., those containing the keywords) and iteratively explores comparisons that involve these records. For ordering entities, SearchER considers not only the ordering attribute, but also the number of keywords that are associated to the entities. For example, considering Query 1, it may happen that an entity with a low price containing all the keywords is emitted before an entity with a high price, but that does not contain all the keywords. In other words, we assume that the keywords are more important than the ordering for the user. For this reason, we say that the nal solution is approximate, since the nal ordering might not be completely respected.
We also built a rst experimental prototype of SearchER and tested it with some queries on two real-world datasets. This very preliminary result does not intend to show the e cacy of our method in general, yet it allows us to showcase that such an approach to ER is actually feasible and promising.
The reminder of this paper is organized as follows: Section 2 introduces the preliminaries; Section 3 describes the envisioned SearchER method; Section 4 reports our preliminary experiments on two real-world datasets; Section 5 describes main related work; nally, Section 6 concludes the paper and discusses the ongoing and future work. 2
To perform ER, the nave comparison of all possible pairs of records has a
quadratic complexity, thus for scaling to large datasets blocking techniques are
generally employed [
An approach that has been shown to achieve high accuracy is meta-blocking, which operates on large and overlapping blocks, restructuring them to lter out non promising comparisons.
Meta-blocking relies on the assumption that the matching likelihood of any two records is analogous to their degree of co-occurrence in a block collection. This means that a block collection B has to be generated by a blocking method that yields redundancy-positive blocks, where the similarity of two records is proportional to the number of blocks they share.
Based on redundancy, which is common for blocking methods [
For the problem of progressive search-driven ER, we propose a revised and extended version of the blocking graph model, as explained in Section 3. 3
At its core, SearchER employs a blocking function to generate the block collection that is exploited for building blocking graph. In the following we describe the novel node-weighting and edge-weighting strategies employed by SearchER for building the blocking graph, and nally we describe how the blocking graph is employed by SearchER for the query evaluation.
Revised node weighting: The nodes are weighted according to the likelihood of appearing in the nal solution. This introduces the concept of RecordRelevance; the intuition is explained with the following example: Example: Consider Query 1, issued by a user that is looking for iPhone entities and requires the results to be generated progressively, from the most expensive to the cheapest ones. Say that a record r1 refers to entity "1 and has a high price. Say also that r1 has many edges connecting it to many records with low prices, and that these edges have a high matching likelihood. So, it is likely that the nal (resolved) price of "1 will not be high. This means that it is likely that "1 will not belong to the nal solution. Hence, the Record-Relevance (i.e., the node-weight) of r1 should be low.
Record-Relevance computation: The Record-Relevance is assessed by
adapting tf-idf [
Revised edge weighting: The weight of the edges captures the likelihood of
a ecting the nal solution. The weighting schema considers both the matching
likelihood of an edge (as in meta-blocking [
The Edge-Relevance also depends on the resolve function employed by the user. For the intuition consider the following example: Example: Consider Query 1. Say that r1 (with a high price r1:year) is connected to another record r2 (with r2:year r1:year). Then, the Record-Relevance of r1 (and r2) should change on the basis of the resolve function: if the resolve function assigns MAX(r1:year; r2:year) as nal price of the entity, it is more likely for r1 (and r2) to be part of the answer for Query 1; which is not true if the resolve function assigns MIN(r1:year; r2:year) as nal price.
Edge-Relevance computation: The Edge-Relevance between two nodes is
computed as the weight in a traditional blocking graph, normalized by the relative
variation (e.g., price = ri:year rj:year) of the attribute value that is
employed for the ordering clause. The edge weight has to be stored also with a
sign that indicates the direction of the variation: a positive value means that
the value of the adjacent node ri with the smaller id is greater than the other
node rj with a higher id (i.e., i < j)|this is just a convention, it could be the
other way around. Thus, the edge weight can be interpreted di erently on the
basis of the resolve function (e.g., MIN/MAX price of the matching records).
Query evaluation: Processing a user's query, the blocking graph is not built
in its entirety (i.e., considering all the records/nodes); instead, only the portion
of the graph that is valuable for the query is considered. In fact, given a block
collection, the node-centric subgraph of the blocking graph for any node ri (i.e.,
the subgraph involving ri and its neighbours only) can be e ciently built using
algorithms described in [
When looking at the obtained blocking graph, we observe in preliminary experiments that for queries with a limited number of keywords (ideally the vast majority), many nodes tend to have the same weights. SearchER divides them into levels and resolves the records starting from the highest levels and sorts the comparisons within each level according to their edge-weights. As soon as a node is evaluated (i.e., all the comparisons involving it have been performed), the resulting entity is emitted.
We devised a prototype of SearchER that takes advantage of the proposed data
model and performed preliminary experiments by issuing keyword queries on
top of two well-known, real-world datasets (for which the ground-truth of the
matching records is known). The rst dataset is CDDB [
In the following we report the results obtained for the following queries: q1: \Rock" q2: \Rock and Roll" q3: \Genetic Algorithms Applications" q4: \Arti cial Intelligence" q5: \Jazz Music" Ordering: Year Sort: DESCENDING issued on CDDB issued on CDDB issued on CORA issued on CORA issued on CDDB
For each query, the entities are sorted by descending values of the attribute year for
both the datasets. As resolve function we employed M AX(ri:year; rj:year), yet very
similar results have been obtained employing M IN (ri:year; rj:year). In our evaluation
we consider as baselines: Standard Blocking (SB) and Sorted Neighbour (SN), with the
same con gurations of [
The results show that SearchER starts emitting entities much earlier (in terms of compared pairs) than the other methods; this is because traditional blocking techniques have to wait until the last comparison in order to evaluate the user query. Surprisingly, we observe that for some queries (q3 and q4 in Figure 2c,d), the baselines cannot identify as many matches as SearchER. This is due to the underlying blocking techniques that fail to yield some of the candidates that are actually matches, and which are correctly identi ed as such in the blocking graph.
Similarly, for query q5, we report the number of entities found, in function of the number of comparisons (Figure 3a) and in function of the time (Figure 3b). Showing that the advantage of SearchER is evident also considering the execution w.r.t. execution time. 5
Query Driven Approach|To avoid the ER evaluation on the whole dataset
before answering any query, recent works proposed a Query Driven Approach (QDA) to
ER [
Thus, Query 1, where the relevance ordering is expressed through an ORDER BY clause, will force QDA to resolve all the entities in the dataset and then sort them by price. Furthermore, QDA strictly relies on batch blocking, which is employed as initial step of the ER. Hence, adapting QDA to work in a pay-as-you-go fashion is not trivial. 6
In this paper, we have presented a preliminary study of the problem of progressive search-driven Entity Resolution, namely the task of deduplicating records of a dirty dataset by following a user query that expresses: (i) the keywords representing the entities of interest (e.g., \Apple iPhone 8"); (ii) the ordering of interest (e.g., from the most expensive to the cheapest). We have proposed a rst solution for solving this problem, and proposed an approximate method, called SearchER.
We believe that the proposed method paves the way for further investigation of the problem. In particular, we are currently devising a method to provide an exact
Pietrangelo et al.
solution for a wide range of resolution function; e.g., w.r.t. Query 1:
minimum=maximum=user def ined f unction([price]) for determining the nal price of an
entity. We are also investigating how to exploit di erent blocking techniques (other than
Standard Blocking and meta-blocking) and advanced similarity functions for the
matching phase [