Entity resolution (ER) is a process to identify records that stand for the same real-world entity. Although automatic algorithms aiming at solving this problem have been developed for many years, their accuracy remains far from perfect. Crowdsourcing is a technology currently investigated, which leverages the crowd to solicit contributions to complete certain tasks via crowdsourced marketplaces. One of its advantages is to inject human reasoning to problems that are still hard to process for computers, which makes it suitable for ER and provides an opportunity to achieve a higher accuracy. As crowdsourcing ER is still a relatively new area in data processing, this paper provides an overview and a brief classification of current research state in crowdsourcing ER. Besides, some open issues are revealed that will be a starting point for our future research.
Theory
Entity resolution (ER) is a process to identify records that
refer to the same real-world entity. It plays a vital role not
only in traditional scenarios of data cleaning and data
integration, but also in web search, online product comparisons,
etc. Various automatic algorithms have been developed in
order to solve ER problems, which generally include two
classes of techniques: similarity-based and learning-based
approaches. Similarity-based techniques use similarity
functions, where values of record pairs similarity is above a
preset threshold are considered to be matched. Learning-based
techniques use machine learning modeling ER as a
classification problem and are training classifiers to identify matching
and non-matching record pairs [
Crowdsourcing was first introduced in the year of 2006 [
The rest of the paper is organized as follows. As crowdsourcing is still not fully established as a technology in the database community, in Section 2 background information on crowdsourcing ER are presented. Then in Section 3, the current state of the research in crowdsourcing ER is presented, different research approaches are classified and compared. After that, open issues are presented in Section 4. Finally, a conclusion is presented in Section 5. 2.
In their early days, computers were mainly used for specific domains that required strong calculation powers. But up until today many tasks, especially those requiring complex knowledge and abstract reasoning capabilities, are not well supported by computers. Crowdsourcing derives its name from “crowd” and “sourcing”, as it outsources tasks to the crowd via the Internet. Many crowdsourced marketplaces, which are represented for instance by Amazon’s Mechanical Turk (MTurk), provide convenience for companies, institutions or individuals recruiting large numbers of people to complete tasks that are difficult for computers or cannot performed well by computer with acceptable effort. Entity resolution is one of such tasks, which can apply crowdsourcing successfully. People are better at solving ER than computers due to their common sense and domain knowledge. For example, for “Otto-von-Guericke-University” and “Magdeburg University” it is easy for people around Magdeburg to know that both of them refer to the same university, while for computer algorithms they are very likely to be judged as different universities. The tasks on MTurk are called Human Intelligence Tasks (HITs). Figure 1 depicts a possible HIT example of ER. One HIT is usually assigned several workers to guarantee the result quality. Small amounts of money, e.g. 3-5 cents are typical at MTurk, are paid for each worker per HIT.
The current research on crowdsourcing and databases
covers two aspects (see Figure 2): on the one hand, databases
should be adjusted to support crowd-based data
processing (see [
Figure 3 presents a classification for the main research on
crowdsourcing ER. From the perspective of crowdsourcing,
most of the researches uses crowdsourcing only for
identifying matching record pairs. Only one recent approach
proposes leveraging crowdsourcing for the whole process of
ER, which gives a novel and valuable view on crowdsourcing
ER. The workflows of approaches, which leverage
crowdsourcing solely for identifying matching record pairs, vary
widely. In general, the workflow of crowdsourcing ER has
been developed step by step. From the beginning, ER is
proposed to be solved by crowdsourcing only, until now a
much more complete workflow is formed by integrating
different research (see Figure 4). In addition, these approaches
focus on different problems. Many novel ideas and
algorithms have been developed to optimize crowdsourcing ER.
Gokhale et al. presented the Corleone approach and tried to
leverage crowdsourcing for the whole process of ER, which
is described as hands-off crowdsourcing [
In Subsection 3.1 the research leveraging crowdsourcing only for the identification of matching record pairs is described. The corleone approach, which leverages crowdsourcing for the whole process of ER, is then discussed in Subsection 3.2. 3.1
Figure 4 depicts a complete hybrid workflow for ER, which
contains all proposals to optimize the workflow in
crowdsourcing ER. Instead of letting crowds answer HITs that
contain matching questions for all records, the first step in
the complete workflow is to choose a proper machine-based
method to generate a candidate set that contains all record
pairs with their corresponding similarities. Then pruning
is performed to reduce the total number of required HITs.
In order to further reduce the number of required HITs, the
transitive relation is applied in the procedure of
crowdsourcing, i.e., if a pair can be deduced by transitive relation, it
does not need to be crowdsourced. For instance, given three
records a, b, and c, the first type of transitive relation is,
if a matches b and b matches c, then a matches c. The
other type of transitive relation means, if a matches b and
b does not match c, then a does not match c. After all
record pairs are further identified by crowdsourcing or
transitive relations, a global analysis can be performed on the
initial result. The global analysis was suggested by Whang
et al. [
The three segments in the dashed box are optional, i.e., in
some research, some of them are not included. In the
following, specific workflows for different approaches are presented
and their contributions are summarized. One important
assertion needs to be pointed out: most of the research is
done given the assumption that people do not make
mistakes when answering HITs. Therefore, each HIT is only
assigned to one worker. The problems caused by mistakes
that crowds may make are addressed for instance in [
Marcus et al. proposed to solve ER tasks only based on
crowdsourcing [
the basic interface of crowdsourcing ER is similar to Figure 1, which asks workers to answer only one question in each HIT and is called simple join. The question in simple join is pair-based, i.e., ask workers whether two records belong to the same entity. For a task to identify the same entities from two sets of records respectively with m and n records, m*n HITs are needed. Two optimizations are provided. One is called naive batching. It asks workers to answer b questions in each HIT. Each question in it is also pair-based. In this way, the total amount of HITs is reduced to (m*n)/b. The other one is called smart batching. Instead of asking workers whether two records belong to the same entity or not, it asks workers to find all matching pairs from two record lists. If the first list contains a records that are selected from one data set and the second list contains b records that are selected from the other data set, the total number of HITs are (m*n)/(a*b).
Feature filtering optimization:.
for some kinds of records, certain features are useful for being join predicates. For instance, there are two groups of people photos, and if each photo is labeled with the gender of the person on it, only photos with a matching gender are necessary to be asked. The feature should be extracted properly, or it leads to large amounts of unnecessary label work and is unhelpful to reduce the total number of HITs.
Even though the above described optimization methods are applied for ER, the crowd-based only workflow cannot satisfy the development for larger and larger data sets. Therefore, the research in rest of this subsection tends to develop a hybrid workflow for crowdsourcing ER. 3.1.2
out Considering Transitive Relation During the
Wang et al. proposed an initial hybrid workflow [
A cluster-based HIT consists of a group of k individual records rather than pairs but based on the given pairs. Wang et al. defined the cluster-based HIT generation formally and proves that this problem is NP-hard. Therefore, they reduced the cluster-based HIT generation problem to the k-clique edge covering problem and then apply an approximation algorithm to it. However, this algorithm fails on generating a minimum number of HITs. Therefore, a heuristic two-tiered approach is proposed to generate as few as possible cluster-based HITs. In addition, the following conclusion is made according to their own experimental results. 1. The two-tiered approach generates fewer cluster-based
HITs than existing algorithms. 2. The initial hybrid workflow achieves better accuracy than machined based method and generates less HITs than the crowd-based only workflow. 3. The cluster-based HITs provide less latency than pair
Wang et al. proved that cluster-based HITs have lower latency than pair-based HITs under the premise of reaching the same accuracy as pair-based HITs, which provides a baseline to prefer cluster-based methods for HIT design. However, the introduced approximation algorithm performs worse than a random algorithm, so it is not presented in this paper.
Whang et al. added a global analysis step to the initial
workflow introduced above by Wang et al., but they did not
consider using transitive relations to reduce the number of
HITs either [
Vesdapunt et al. [
The number of HITs is significantly effected by the labeling order because of applying transitive relations for crowdsourcing ER, i.e. in their work Vesdapunt et al. suggest to first ask crowds questions for real matching record pairs and then for real non-matching record pairs. Because whether two records match or not in reality cannot be known, HITs are first generated for record pairs with higher matching probabilities. However, the latency that a question is answered by crowdsourcing is long, and it is not feasible to publish a single record pair for crowdsourcing and wait for its result to decide whether the next record pair can be deduced or has to be crowdsourced. In order to solve this problem, a parallel labeling algorithm is devised to reduce the labeling time. This algorithm identifies a set of pairs that can be crowdsourced in parallel and asks crowds questions about these record pairs simultaneously, then iterates the identification and crowdsourcing process according to the obtained answers until all record pairs are resolved. The proposed algorithm is evaluated both in simulation and a real crowdsourcing marketplace. The evaluation results show that its approaches with transitive relations can save more monetary costs and time than existing methods with little loss in the result quality.
However, Vesdapunt et al. proved that the algorithm proposed by Wang et al. may be Ω(n) worse than optimal, where n is the number of records in the database. This proof means the algorithm is not better than any other algorithms, because Vesdapunt et al. also prove that any algorithm is at most Ω(n) worse than optimal. Therefore, Vesdapunt et al. presented their own strategies to minimize the number of HITs considering transitive relations in the process of crowdsourcing. One simple strategy is to ask crowds questions of all record pairs in a random order without considering the matching probabilities of record pairs. Although this strategy is random, it is proved that it is at most o(k) worse than the optimal, where k is the expected number of clusters. For both approaches a graph-clustering-based method is adopted to efficiently show the relations among possibly matching records. Since the expected number of clusters cannot exceed the number of records, the random algorithm is better than the algorithm proposed by Wang et al. Another strategy called Node Priority Querying is also proved to be at most o(k) worse than the optimal. These algorithms are evaluated using several real-world data sets. The results in different data sets are not stable. However, overall the node priority algorithm precedes the random algorithm and the algorithm proposed by Wang et al. The random algorithm is superior to the algorithm proposed by Wang et al. in some cases.
In summary, both Vesdapunt et al. and Wang et al. considered transitive relations during the process of crowdsourcing, which opens a new perspective to further decrease the number of HITs to reduce the latency and lower the monetary cost. However, their proposed algorithms perform not stably on different data sets and can be optimized or redesigned. 3.2
All approaches introduced so far apply crowdsourcing only
for identifying whether record pairs are matching or not.
The proposed algorithms have to be implemented by
developers. Nowadays, the need for many enterprises to solve
ER tasks is growing rapidly. If enterprises have to employ
one developer for each ER task, for so many tasks the
payment for developers are huge and not negligible. Even in
some cases, some private users cannot employ developers
to help them complete ER tasks by leveraging
crowdsourcing, as they have only a small amount of money. In order to
solve this problem, Gokhale et al. proposed hands-off
crowdsourcing for ER, which means that the entire ER process is
completed by crowdsourcing without any developer [
In this section, open issues on crowdsourcing ER are presented that are from the authors perspective the most important ones to be addressed by future research.
Machine-based methods and pruning approaches: The machine-based methods used in most approaches are similarity-based and pruning methods are simply abandoning the record pairs, whose matching probabilities are above or below given thresholds. Such approaches cannot get satisfactory results in the case of more and more complex data environments, because record pairs with very high matching probabilities may refer to different entities, and vice versa. Therefore, machinedbased methods should be extended to learning-based and pruning approaches should be rigorously designed to avoid abandoning the record pairs, which indeed need to be further confirmed.
Only transitive relations applied: currently, transitive relations have been widely adopted in crowdsourcing ER, which are not considered at the early stage of crowdsourcing ER. Other techniques such as correlation clustering could be applied to ER.
Limited comparability of results: both [
Only initial optimization strategies: as leveraging crowdsourcing for the whole process of ER, i.e., hands-off crowdsourcing, is just in the beginning of its devopment. The following optimization techniques can be developed: first, the current hands-off crowdsourcing for ER is based on the setting of identifying record pairs from two relational tables, which may be extended to other ER scenarios. Second, the current strategy to extract samples for generating blocking rules is quite simple, and better sampling strategies should be explored.
Ontologies and indexes: once a decision is made, the knowledge injected by the crowd is widely lost. Another interesting possible research question could be, how this feedback could be gathered and described for instance by an ontology.
This paper gives an overview of the current research state in crowdsourcing ER. Most of the approaches focus on leveraging crowdsourcing to verify the matching of record pairs. From the early stage of the research to more recent approaches, the workflow was optimized step by step and more aspects were considered for the process of crowdsourcing, which developed from crowd-based only workflow to hybrid computer-crowdsourcing workflow, which considers transitive relations. However, this does not mean that the research on the initial workflow is less significant. In contrast, every approach is valuable and contributes to various research aspects of crowdsourcing ER.
Most recently, a novel perspective to crowdsourcing is proposed, which extends the crowdsourcing object and leverages crowdsourcing not only to verify the matching of record pairs, but also to implement the algorithms, train a learningbased matcher, estimate the matching accuracy and even implement an iteration process. This novel idea makes the crowdsourcing more applicable and further reduces the cost for employing dedicated people.
In Section 4, some important open issues are presented. My future work will focus on the first possible research direction, i.e., exploring techniques to be applied in crowdsourcing ER, such as correlation clustering.
I would like to thank the China Scholarship Council to fund this research. I also express my gratitude to Eike Schallehn and Ziqiang Diao for their precious feedback. 2013.