PaperlayerView exact revision on arXiv

Source-linked AI summary

Leveraging Transitive Relations for Crowdsourced Joins

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

arXiv:1408.6916v2cs.DB

TL;DR

Crowdsourced joins must verify machine-generated candidate pairs, but existing methods overlook transitive relations that can determine some labels without human review. This paper develops a hybrid framework with ideal and heuristic ordering plus parallel labeling, and reports substantial money and time savings with a little loss in result quality.

  • Problem

    Existing hybrid crowdsourced joins publish all machine-generated candidate pairs for verification instead of exploiting transitive relations among their labels.

  • Method

    The framework orders candidate pairs for verification, uses transitive relations to deduce labels, and parallelizes crowdsourcing with performance optimizations.

  • Results

    The approaches save much more money and time than existing methods, with a little loss in result quality, based on simulation and AMT evaluations.

  • Takeaways & Limitations

    Transitive relations can produce significant cost savings in crowdsourced joins for entity resolution.

  • Takeaways & Limitations

    The ideal labeling order cannot be achieved in reality because the true matching pairs are unknown upfront.

Abstract

from arXiv · show

The development of crowdsourced query processing systems has recently attracted a significant attention in the database community. A variety of crowdsourced queries have been investigated. In this paper, we focus on the crowdsourced join query which aims to utilize humans to find all pairs of matching objects from two collections. As a human-only solution is expensive, we adopt a hybrid human-machine approach which first uses machines to generate a candidate set of matching pairs, and then asks humans to label the pairs in the candidate set as either matching or non-matching. Given the candidate pairs, existing approaches will publish all pairs for verification to a crowdsourcing platform. However, they neglect the fact that the pairs satisfy transitive relations. As an example, if $o_1$ matches with $o_2$, and $o_2$ matches with $o_3$, then we can deduce that $o_1$ matches with $o_3$ without needing to crowdsource $(o_1, o_3)$. To this end, we study how to leverage transitive relations for crowdsourced joins. We propose a hybrid transitive-relations and crowdsourcing labeling framework which aims to crowdsource the minimum number of pairs to label all the candidate pairs. We prove the optimal labeling order in an ideal setting and propose a heuristic labeling order in practice. We devise a parallel labeling algorithm to efficiently crowdsource the pairs following the order. We evaluate our approaches in both simulated environment and a real crowdsourcing platform. Experimental results show that our approaches with transitive relations can save much more money and time than existing methods, with a little loss in the result quality.

1. INTRODUCTION

The paper combines machine-generated candidate pairs with crowdsourcing and transitive relations to reduce verification effort in entity-resolution joins. It proves an ideal labeling order, develops practical heuristic and parallel methods, and reports savings in money and time with a small quality loss.

  • Motivation: Crowdsourced joins use humans to determine which object pairs from two collections refer to the same real-world entity.The paper focuses on entity resolution and motivates the task with product records from online retailers.
  • Motivation: Hybrid approaches first generate candidate matching pairs with machines, but existing methods publish all candidates for human verification.This motivates reducing the number of pairs sent to a crowdsourcing platform.
  • Framework: The proposed framework uses transitive relations to label all candidate pairs while crowdsourcing the minimum number of pairs.The paper identifies labeling order as a major determinant of total crowdsourced pairs.
  • Labeling order: The ideal order labels all matching pairs before the remaining non-matching pairs, while the practical heuristic sorts pairs by decreasing matching likelihood.The ideal order assumes knowledge unavailable in reality; likelihoods can come from machine-learning methods.
  • Parallel labeling: A parallel labeling algorithm crowdsources pairs concurrently, with two optimization techniques proposed to improve performance further.The parallel design addresses the latency of sequentially publishing pairs.
  • Evaluation: Simulated and AMT evaluations report substantially lower money and time costs than existing methods, with a little loss in result quality.The evaluation includes both a simulated environment and a real crowdsourcing platform.

2. PROBLEM FORMULATION

The paper formulates crowdsourced join labeling as minimizing paid pair verifications while using graph-based transitive relations to deduce other labels. It defines the relation rules, candidate-pair setting, and a running example of reducing required crowdsourcing.

  • 2. PROBLEM FORMULATION: The problem formulation introduces crowdsourcing, transitive relations, and the task of labeling candidate pairs generated for a join.These topics organize the problem formulation around how human labels and deductions interact.
  • 2.1 Crowdsourcing: A crowdsourcing HIT asks workers whether two objects are identical, returning a matching or non-matching label.The example HIT compares “iPad 2” and “iPad two” and requests YES or NO.
  • 2.1 Crowdsourcing: The paper assumes correct worker answers, treating worker errors and question ambiguity as an orthogonal issue addressed by other techniques.This assumption applies for the remainder of the paper.
  • 2.2 Transitive Relations: The graph representation uses objects as vertices and labeled pairs as edges to test whether an unlabeled pair can be deduced.The rules generalize across sequences of objects through Lemma 1.
  • 2.2 Transitive Relations: Positive transitivity deduces a match across a path of matching pairs, while a path containing one non-matching pair deduces a non-match.If every path contains more than one non-matching pair, the label cannot be deduced.
  • 2.3 Problem Description: Machine techniques first generate candidate matching pairs, after which some labels are crowdsourced and others are deduced through transitive relations.Because crowdsourced pairs incur financial cost, the formal goal is to minimize the number directly labeled.
  • 2.3 Problem Description: In the running example, seven direct labels can be reduced to six because another pair is deduced from previously labeled matching pairs.The text identifies six as the optimal amount for the example.

3. LABELING FRAMEWORK

The framework combines sorting and labeling to minimize crowdsourced pairs by exploiting transitive relations, then uses ClusterGraph-based deduction and parallel labeling to reduce latency without increasing pair count.

  • Framework: The framework takes machine-generated unlabeled candidate pairs and identifies their labels through crowdsourcing or transitive relations.It consists mainly of Sorting and Labeling components.
  • Sorting Component: The labeling order affects the number of crowdsourced pairs, so the sorting component outputs an order intended to minimize that number.The framework labels pairs in the resulting sorted order.
  • Deduction: Matching pairs are merged into clusters, while non-matching pairs become edges between clusters in a ClusterGraph for efficient deduction.The graph is built using Union-Find; matching within a cluster, one inter-cluster edge, or no edge determines the deduction outcome.
  • Deduction: A pair can be deduced when its objects share a cluster or when different clusters are connected by an edge; otherwise it must be crowdsourced.This corresponds respectively to a matching label, a non-matching label, or no deduction.
  • Labeling Component: The simple one-pair-at-a-time method causes long latency and cannot use batching, whereas the parallel algorithm crowdsources multiple pairs without increasing the total number crowdsourced.The parallel approach addresses both simultaneous worker activity and the associated money cost described for the simple approach.

4. SORTING

This section formulates labeling-order optimization for crowdsourced pairs, proves that matching pairs should precede non-matching pairs, and develops expected-order heuristics when true labels are unknown.

  • Expected order: The ideal optimal order cannot be achieved directly because the matching status of pairs is unknown before labeling.The paper therefore considers an expected optimal order and a practical heuristic.
  • Problem formulation: The goal is to find a labeling order minimizing the number of crowdsourced pairs.For an order ω, C(ω) denotes the required number of crowdsourced pairs.
  • Optimal labeling order: Swapping a non-matching pair before a matching pair never increases the number of crowdsourced pairs.Adjacent swaps can therefore transform an order while preserving or reducing its crowdsourcing cost.
  • Optimal labeling order: The optimal labeling order labels all matching pairs first and all non-matching pairs afterward.This follows from the adjacent-swap argument and minimizes C(ω).
  • Expected order: In the three-pair example, orders ω1 and ω4 both minimize the expected number of crowdsourced pairs at 2.09.The other listed orders have expected costs of 2.17 or 2.83.
  • Expected order: The heuristic labels pairs in decreasing order of their machine-estimated likelihood of being matching.The expected-order problem is described as NP-hard, motivating this likelihood-based approach.

5. PARALLEL LABELING

The parallel labeling algorithm identifies pairs that must be crowdsourced in each iteration, publishes them simultaneously, and uses their labels to deduce subsequent pairs. Two optimizations increase parallelism while preserving the required number of crowdsourced pairs.

  • Parallel labeling algorithm: The algorithm iteratively identifies pairs that cannot be deduced from earlier pairs, crowdsources them simultaneously, and uses their labels to process later pairs.This repeats until all pairs are labeled.
  • Parallel labeling algorithm: Pairs are selected by scanning the sorted labeling order while maintaining a ClusterGraph of labeled relationships and non-matching edges.The graph is updated incrementally rather than rebuilt from scratch for each pair.
  • Parallel labeling algorithm: In the example’s first iteration, five pairs—p1, p2, p3, p5, and p6—are identified for parallel crowdsourcing.Pair p7 is omitted because it can be deduced under the assumption that unlabeled pairs are matching.
  • Parallel labeling algorithm: In the second iteration, the remaining pair p7 is crowdsourced, after which all pairs are labeled and the algorithm terminates.The algorithm publishes p7 after determining it cannot be deduced from the preceding pairs.
  • Optimization techniques: Instant decision publishes newly eligible pairs whenever any published pair is labeled, while non-matching first prioritizes published pairs least likely to match.These techniques increase available parallelism during execution.

6. EXPERIMENT

Experiments on two real-world datasets show that transitive relations reduce crowdsourcing demands, while labeling order and parallel execution further affect efficiency. AMT results indicate substantial cost and time savings, with quality trade-offs depending on the dataset.

  • Effectiveness of transitive relations: 95% fewer crowdsourced pairs were required on Paper with Transitive than Non-Transitive; at threshold 0.3, the counts were 1,065 versus 29,281.On Product, Transitive saved about 20% of crowdsourced pairs despite fewer matching objects.
  • Labeling orders: Labeling order substantially affected crowdsourcing volume: Worst Order required 139,181 pairs on Paper at threshold 0.1, about 26 times Optimal Order.Expect Order required only a few more pairs than Optimal Order, while Random Order required substantially more.
  • Parallel labeling: Parallel labeling reduced Paper's iterations from 1,237 to 14 for 1,237 crowdsourced pairs at threshold 0.3.Higher likelihood thresholds produced fewer iterations because fewer pairs were available and the graph became sparser.
  • Parallel optimizations: Instant-decision optimizations kept sufficient pairs available on the crowdsourcing platform, allowing workers to continue labeling without waiting for each batch to finish.Parallel(ID) and Parallel(ID+NF) maintained pair availability more continuously than Parallel.

7. RELATED WORK

Prior work covers crowdsourced queries, hybrid human-machine joins, transitive-relation use, and parallel crowdsourcing frameworks. Existing transitive-relation applications primarily address conflict resolution, whereas this paper targets reducing human effort.

  • Crowdsourced query processing: Crowdsourced query research includes MAX, SELECT, JOIN, crowd-enabled query processing, and hybrid crowd-machine data integration systems.Crowdsourced joins have been studied using human-only, hybrid, probabilistic, and budget-based approaches.
  • Transitive relations: Entity-resolution applications use transitive relations after labeling pairs, but mainly study conflicts introduced by transitivity rather than minimizing human effort.This distinguishes the paper's focus on reducing the number of pair verifications.
  • Parallel crowdsourcing: Parallel crowdsourcing research compares iterative and parallel models and provides toolkits or frameworks for executing subtasks concurrently.Examples include TurKit's crash-and-rerun model and CrowdForge's map-reduce-style task partitioning.

8. CONCLUSION AND FUTURE WORK

The paper combines machine-based pair ordering with transitive-relation labeling and parallel execution to reduce crowdsourced join verification. Experiments using simulation and AMT report significant cost savings with little or no quality loss, while future work broadens the scope beyond the current setting.

  • Contributions: The sorting component orders machine-generated candidate pairs, while the labeling component uses parallel crowdsourcing to reduce latency and cost.The optimal order labels matching pairs first, but the practical heuristic orders pairs by decreasing matching probability.
  • Findings: Simulation and AMT evaluations show that transitive relations can produce significant cost savings with no or little loss in result quality.The conclusion summarizes the reported benefits across both evaluation settings.
  • Future work: Future work includes detecting non-transitive relations, automating money/time/quality trade-offs, exploring one-to-one relations, and extending to general theta-joins.The current demonstrated scope is crowdsourced joins for entity resolution using transitive relations.
Loading 1408.6916v2…