PaperlayerView exact revision on arXiv

Source-linked AI summary

CrowdER: Crowdsourcing Entity Resolution

Jiannan Wang, Tim Kraska, Michael J. Franklin, Jianhua Feng

arXiv:1208.1927v1cs.DB

TL;DR

Entity resolution is important for integrating and cleaning data, but machine methods remain imperfect and human verification is costly and slow at scale. CrowdER combines machine pruning with targeted human verification and develops heuristic HIT generation. Experiments report good efficiency and high accuracy compared with machine-only or human-only alternatives.

  • Problem

    Machine-only entity resolution remains imperfect, while human-only verification is expensive, slow, and infeasible at moderate scale.

  • Method

    CrowdER uses machine techniques to discard dissimilar pairs, sends likely matches to the crowd, and generates cluster-based HITs with a two-tiered heuristic.

  • Results

    CrowdER achieves good efficiency and high accuracy compared with machine-only or human-only alternatives in experiments on real datasets using AMT.

  • Takeaways & Limitations

    The hybrid approach makes it practical to bring humans into the entity-resolution process while reducing cost and maintaining good answer quality.

  • Takeaways & Limitations

    For datasets with millions of records, many remaining pairs may still require crowd verification, motivating further machine offloading and budget-aware tradeoffs.

Abstract

from arXiv · show

Entity resolution is central to data integration and data cleaning. Algorithmic approaches have been improving in quality, but remain far from perfect. Crowdsourcing platforms offer a more accurate but expensive (and slow) way to bring human insight into the process. Previous work has proposed batching verification tasks for presentation to human workers but even with batching, a human-only approach is infeasible for data sets of even moderate size, due to the large numbers of matches to be tested. Instead, we propose a hybrid human-machine approach in which machines are used to do an initial, coarse pass over all the data, and people are used to verify only the most likely matching pairs. We show that for such a hybrid system, generating the minimum number of verification tasks of a given size is NP-Hard, but we develop a novel two-tiered heuristic approach for creating batched tasks. We describe this method, and present the results of extensive experiments on real data sets using a popular crowdsourcing platform. The experiments show that our hybrid approach achieves both good efficiency and high accuracy compared to machine-only or human-only alternatives.

1. INTRODUCTION

Entity resolution finds records referring to the same entity, but machine-only methods remain imperfect and human-only processing is costly at scale. CrowdER combines machine pruning with human verification and develops a heuristic HIT-generation strategy for efficient, accurate resolution.

  • Motivation: Entity resolution identifies different records that refer to the same real-world entity for data cleaning and integration.Records can differ textually while representing the same product.
  • Motivation: Machine-based techniques remain imperfect, while crowdsourcing can improve insight but is slower and more expensive.These limitations motivate combining algorithmic and human-based approaches.
  • Motivation: A naive human workflow creates O(n^2) HITs, and batching alone does not make entity resolution scalable.Prior batching reduces HIT counts, but the resulting human-only approach remains insufficient for moderate-sized datasets.
  • CrowdER: CrowdER first discards dissimilar record pairs with machine techniques and sends only likely matches to the crowd for verification.The approach uses human resources for cases where human insight is needed.
  • Contributions: The paper proves minimum cluster-based HIT generation is NP-Hard and develops a two-tiered heuristic solution.It also compares pair-based and cluster-based generation analytically and experimentally.
  • Evaluation: Experiments on real datasets using AMT show reduced cost, good answer quality, and practical use of humans in entity resolution.The implemented approaches are compared with state-of-the-art techniques.

2. ENTITY RESOLUTION TECHNIQUES

Entity resolution techniques use similarity scores or learned classifiers to identify matching records, while CrowdER combines machine estimates with targeted crowd verification. Its workflow prunes low-likelihood pairs before generating HITs, reducing the verification burden.

  • Similarity-based techniques: Similarity-based methods compute a similarity value for record pairs and classify pairs meeting a threshold as referring to the same entity.The similarity value increases with record similarity.
  • Similarity-based techniques: Jaccard similarity is computed as set intersection size divided by set union size; the example pair r1,r2 scores 0.57.With a threshold of 0.5, r1,r2 is considered a match.
  • Learning-based techniques: Learning-based methods represent record pairs as feature vectors, train classifiers on matching and non-matching examples, and label new pairs.Feature dimensions correspond to similarity values across selected attributes and functions.
  • Hybrid workflow: CrowdER computes each pair’s likelihood of referring to the same entity and sends only pairs exceeding a threshold to the crowd.The workflow then generates HITs for human matching decisions.
  • Hybrid workflow: In the nine-record example, pruning at threshold 0.3 reduces 36 possible pairs to 10 pairs requiring verification.Batching two pairs per HIT then produces five HITs.

3. HIT GENERATION

HIT generation groups record pairs or records for crowdsourced verification while limiting cluster size and covering every candidate pair. The cluster-based problem is NP-Hard.

  • HIT Types: Pair-based HITs batch multiple record pairs, while cluster-based HITs ask workers to find duplicates among a group of records.Pair-based interfaces require a decision for each pair; cluster-based interfaces use shared labels to indicate duplicate records.
  • Pair-based HIT Generation: ⌈|P|/k⌉ pair-based HITs are required when each HIT contains at most k candidate pairs.For ten candidate pairs and k = 2, this produces five pair-based HITs.
  • Cluster-based HIT Generation: Cluster-based HIT generation minimizes the number of HITs subject to a maximum of k records per HIT and coverage of every candidate pair.Each candidate pair must occur together in at least one generated HIT.
  • Cluster-based HIT Generation: Three cluster-based HITs cover the ten example pairs with k = 4, and fewer than three cannot satisfy the requirements.The example uses three record groups, each containing at most four records and jointly covering all ten pairs.
  • Complexity: The cluster-based HIT generation problem is NP-Hard.The paper establishes this through a reduction from the k-clique covering problem.

4. APPROXIMATION ALGORITHM

The paper reduces cluster-based HIT generation to k-clique edge covering and applies an approximation algorithm that covers graph edges with bounded-size cliques. In the example, this method uses seven HITs although the optimum uses three.

  • Reduction: A cluster-based HIT is modeled as a clique whose vertices are records and whose covered edges represent candidate pairs verified together.The reduction maps each record to a graph vertex and each pair requiring verification to an edge.
  • Approximation Algorithm: The approximation algorithm constructs a sequence of graph vertices and edges, partitions it into subsequences of k − 1 elements, and generates one k-clique per subsequence.This yields ⌈|SEQ|/(k−1)⌉ cliques covering all graph edges.
  • Example: Seven cluster-based HITs cover the ten example pairs when k = 4 using the approximation algorithm.The graph has ten edges and nine vertices, producing nineteen sequence elements and seven subsequences.
  • Limitation: The approximation algorithm can substantially overproduce HITs: the example optimum requires three, and experiments found it worse than a naive algorithm on tested data sets.This limitation motivates the subsequent two-tiered algorithm.

5. A TWO-TIERED APPROACH

The two-tiered approach partitions large connected components into small, highly connected components and packs those components into bounded-size HITs. Its bottom-tier packing problem is formulated as an integer linear program.

  • Approach Overview: The approach builds a sparse graph, classifies connected components by threshold k, partitions large components, and packs the resulting small components into HITs.Large components exceed the cluster-size threshold and must be partitioned before packing.
  • Approach Overview: Highly connected small components cover more edges per HIT, while packing multiple small components can further reduce the number of HITs.Different packing methods can produce different HIT counts.
  • Top Tier: The top tier greedily initializes each small component with the maximum-degree vertex, then adds vertices maximizing connectivity until reaching k or exhausting candidates.Connectivity is evaluated using indegree and outdegree relative to the current component; ties use minimum outdegree.
  • Top Tier: The top tier repeats component construction and removes covered edges until each large connected component is partitioned.For the Figure 5 example, the large component is partitioned into three small components.
  • Bottom Tier: The bottom tier packs small connected components into the minimum number of cluster-based HITs under the k-record limit, an NP-Hard cutting-stock variant.The paper formulates this packing task as an integer linear program using feasible HIT patterns.
  • Bottom Tier: A feasible packing pattern specifies how many small components of each size a HIT contains, subject to a total of at most k vertices.For k = 4, the paper illustrates feasible patterns and minimizes the number of selected patterns.

6. BACK OF THE ENVELOPE ANALYSIS

Cluster-based HITs require comparisons based on the HIT’s entity composition and the order in which entities are identified. Grouping duplicates can reduce comparisons substantially, while identifying smaller entities first minimizes the total.

  • Comparison model: The total comparison count depends on both the number of distinct entities and their identification sequence.The same HIT can require different numbers of comparisons depending on entity sizes and ordering.
  • Comparison model: A cluster-based HIT compares a selected record with only records not already assigned to previously identified entities.After identifying e_i, later selections omit records in earlier entities, reducing the comparisons needed at each iteration.
  • Comparison model: With no duplicates, a cluster-based HIT requires n·(n−1)/2 comparisons, whereas an all-duplicate HIT requires n−1.These are the two extreme cases for the number of comparisons in a cluster-based HIT.
  • Ordering effect: The weighted-sum form shows that identifying entities in increasing order of |e_i| minimizes comparisons, while decreasing order maximizes them.The weight (m−i) decreases as i increases, so earlier identification contributes more heavily to the total.
  • Example: For n = 4 records containing a three-record entity and a singleton, the cluster-based HIT requires three comparisons instead of four for a pair-based HIT.The worker checks four relevant record pairs but avoids one comparison because records already assigned to the first entity need not be compared again.

7. EXPERIMENTAL RESULTS

Experiments on real Restaurant and Product datasets show that the two-tiered hybrid workflow reduces verification effort while maintaining strong answer quality. Its benefits depend on threshold, qualification testing, and HIT format, with trade-offs in recall, latency, and worker participation.

  • Experimental Setup: The experiments evaluated two-tiered HIT generation, answer quality against machine baselines, and pair-based versus cluster-based HITs on two real datasets.Restaurant2 contains 367,653 record pairs and 106 matches; Product contains 1,180,452 pairs and 1,097 matches.
  • Experimental Setup: 92.2% recall required crowdsourcing only 8,315 Product pairs, over two orders of magnitude fewer than all 1,180,452 pairs.This result used a likelihood threshold of 0.2.
  • Cluster-based HIT Generation: The two-tiered approach generated the fewest cluster-based HITs across tested likelihood and cluster-size thresholds.At likelihood threshold 0.1 on Product, the random baseline generated 6,422 HITs versus 2,033 for the two-tiered approach.
  • Entity-Resolution Techniques: Hybrid matched SVM quality on Restaurant and substantially outperformed simjoin and SVM on Product.The comparison used precision and recall as result-quality metrics.
  • Entity-Resolution Techniques: Lowering the likelihood threshold increased recall to 99.4% on Product but required crowdsourcing 37,641 pairs.The hybrid workflow therefore exposes a recall-versus-crowdsourcing-effort trade-off.
  • Entity-Resolution Techniques: Qualification tests improved result quality but increased completion time from 4.5 to 19.9 hours on Product.On Restaurant, completion time increased from 1.3 to 1.6 hours for 112 HITs; on Product, the experiments involved 508 HITs.
  • Pair-based vs. Cluster-based HITs: Cluster-based HITs took about 15% less time per assignment than pair-based HITs on Product, but total completion time depended on worker participation and dataset composition.Pair-based HITs finished earlier on Product, whereas cluster-based HITs had an overall advantage for Product+Dup.

8. RELATED WORK

Related work spans automated entity-resolution methods, interactive human labeling, database crowdsourcing systems, blocking, and hybrid systems in other domains. The paper positions its hybrid entity-resolution workflow as an area not previously explored by existing work.

  • Entity Resolution and Human Interaction: Prior entity-resolution research includes automated algorithms, active learning, and systems that incorporate interactive user labeling.Active learning was reported to reduce the training-set size needed for high accuracy.
  • Database Crowdsourcing: Database crowdsourcing systems have extended query languages and workflow systems with crowd-based operators or user-defined functions.Examples include CrowdSQL and CrowdDB, Qurk, and Deco.
  • Hybrid Systems: Hybrid human-machine systems outside databases combine automated processing with human validation or editing for image search and document processing.The cited examples include CrowdSearch and Solyent.
  • Research Gap: The authors state that existing work had not explored hybrid human-machine techniques for improving entity resolution.This positions the paper's contribution at the intersection of crowdsourcing and entity resolution.
  • Blocking: The paper distinguishes cluster-based HIT generation from typical blocking because its block size is constrained by what workers can handle.The related blocking work partitions records to maximize matching pairs co-occurring within partitions.

9. CONCLUSION AND FUTURE WORK

The paper presents hybrid human-machine entity resolution as a response to machine-only quality limitations and the excessive cost and latency of brute-force human verification. It establishes cluster-based HIT generation as NP-Hard, proposes a two-tiered heuristic, and identifies scaling, interface, and privacy as future challenges.

  • Hybrid human-machine entity resolution addresses machine-only quality limitations while avoiding the excessive slowness and expense of brute-force human approaches.
  • The paper formulates cluster-based HIT generation and shows that the problem is NP-Hard.
  • A two-tiered heuristic generated fewer cluster-based HITs than existing algorithms in experiments on real data sets using AMT.
  • Hybrid workflows significantly reduced HIT counts versus human-based techniques and achieved higher quality than state-of-the-art machine-based techniques.
  • Cluster-based HITs can provide lower latency than pair-based HITs when many records match, although AMT workers preferred the simpler pair-based interface.
  • Future work includes scaling to much larger datasets, balancing cost, quality, and latency, and protecting confidential data during crowd processing.
Loading 1208.1927v1…