Human-powered Sorts and Joins

Adam Marcus; Eugene Wu; David Karger; Samuel Madden; Robert Miller

Source-linked AI summary

Human-powered Sorts and Joins

Adam Marcus, Eugene Wu, David Karger, Samuel Madden, Robert Miller

arXiv:1109.6881v1Sep 30, 2011cs.DB

TL;DR

Crowdsourced database workflows require substantial reimplementation and ad-hoc parameter tuning, motivating a declarative system for human-powered operations. Qurk integrates crowd workers into query processing and studies joins and sorts with batching, ratings, comparisons, and pre-filtering. These techniques substantially reduce cost while preserving reported accuracy and latency in the evaluated settings.

Problem
Crowd workflows reimplement common database operations and rely on ad-hoc choices for assignments, payment, and combining human operators.
Method
Qurk is a declarative crowd-query system that implements joins and sorts through worker-facing interfaces, batching, numerical ratings, comparisons, and feature filtering.
Results
Join optimizations reduced cost from $67 to $3, while hybrid sorting achieved τ > .95 accuracy at less than one-third the cost.
Takeaways & Limitations
Batching, feature filtering, and hybrid sorting provide practical cost reductions for human-powered joins and sorts in Qurk.
Takeaways & Limitations
Feature filtering is not always appropriate when its cost is unjustified, its features do not guarantee non-joins, or workers disagree about feature values.

Abstract

from arXiv · show

Crowdsourcing markets like Amazon's Mechanical Turk (MTurk) make it possible to task people with small jobs, such as labeling images or looking up phone numbers, via a programmatic interface. MTurk tasks for processing datasets with humans are currently designed with significant reimplementation of common workflows and ad-hoc selection of parameters such as price to pay per task. We describe how we have integrated crowds into a declarative workflow engine called Qurk to reduce the burden on workflow designers. In this paper, we focus on how to use humans to compare items for sorting and joining data, two of the most common operations in DBMSs. We describe our basic query interface and the user interface of the tasks we post to MTurk. We also propose a number of optimizations, including task batching, replacing pairwise comparisons with numerical ratings, and pre-filtering tables before joining them, which dramatically reduce the overall cost of running sorts and joins on the crowd. In an experiment joining two sets of images, we reduce the overall cost from $67 in a naive implementation to about $3, without substantially affecting accuracy or latency. In an end-to-end experiment, we reduced cost by a factor of 14.5.

1. INTRODUCTION

Qurk brings crowdsourcing into a declarative database workflow to reduce reimplementation and ad-hoc tuning for human-powered relational operations. The paper focuses on joins and sorts and develops optimizations that reduce HITs, cost, and sometimes latency.

MTurk enables workers to perform small data-processing tasks, typically for 1–5 cents per task.
Existing crowd workflows reimplement filtering, sorting, and joining, while conventional database operators cannot directly optimize over crowd workers.
Workflow designers also tune assignment counts, worker payment, and operator combinations ad hoc despite these parameters being suitable for cost-based optimization.
Qurk provides a declarative crowd-query system whose executor selects implementations and combines human computation with traditional relational processing.
The paper systematically studies human-powered joins and sorts, including alternative HIT interfaces and optimizations for batching, worker agreement, pre-filtering, and hybrid sorting.
Qurk extends its earlier system design while reducing join cost from $67 to $3 in the reported optimization example.

2. LANGUAGE OVERVIEW AND SYSTEM

Qurk exposes crowd operations through relational queries and task templates, translating declarative UDFs into worker-facing HITs. Its model supports filtering, generation, ranking, joining, response combination, normalization, and batching.

Qurk uses a relational data model with user-defined scalar and table functions to retrieve data from the crowd.
Predefined task templates let developers specify how questions are presented without implementing most UDFs directly in raw HTML.
Filter UDFs ask workers questions about tuples, while generative UDFs can return normalized multi-field tuples that form new tables.
Multiple worker responses can be combined by MajorityVote or QualityAdjust, which adjusts confidence while identifying spammers and worker bias.
Rank UDFs in ORDER BY clauses support comparison or numerical-rating interfaces, batching, top-K queries, and MAX/MIN aggregates.
EquiJoin UDFs compare pairs from two tables, and Qurk can batch multiple join tasks into one HIT.

3. JOIN OPERATOR

The join operator is evaluated through experiments comparing alternative join implementations and feature filtering. The section frames these experiments around join quality and performance.

The section presents several join implementations and a feature-filtering approach designed to reduce join complexity.
Experiments evaluate the quality and performance of different join approaches.

3.1 Implementation

Qurk implements joins through worker comparisons, batching, and optional feature filtering, while acknowledging limits from ambiguous human judgments and unavailable item keys or orderings.

The basic join asks workers to compare elements from two relations and uses their answers to determine whether pairs satisfy the join condition.
More efficient hash or sort-merge joins are not implemented because Qurk cannot compute item hashes or item order for the relevant data.
Join interfaces generalize beyond images to fields that can be displayed in HTML.
A simple pairwise join requires |R||S| HITs, while batching places multiple pairs in each HIT to reduce the number of HITs.
SmartBatch presents two image columns and lets workers select matching pairs, including an explicit no-match response.
Alternative identifier-labeling joins are outside the paper’s scope because the experiments target batching and combining accuracy-cost tradeoffs.

3.2 Feature Filtering Optimization

Qurk’s feature filtering optimization uses worker-derived feature predicates to reduce join candidates before human comparison, while accounting for filtering cost and reliability. Its benefit depends on filter selectivity, validity, and worker agreement.

Filtering mechanism: Feature predicates are applied in a linear scan to avoid otherwise necessary join cross products and reduce candidate pairs.The POSSIBLY clause retains pairs only when the attempted predicates are satisfied.
Selectivity model: Under independent, non-UNKNOWN filters, σ_i denotes each feature’s selectivity and the combined POSSIBLY-clause selectivity is computed from those feature selectivities.For feature i, σ_i is based on the probability that tables R and S match on that feature.
Filtering benefit: Feature filtering reduces executed join HITs to a fraction Sel of the count produced by the join algorithm alone.The linear passes add cost, but their HITs can be batched through merging and combining.
Filter selection: Filters should be rejected when their added cost outweighs selectivity gains, their feature does not guarantee nonmatching entities, or workers disagree about the feature value.Qurk estimates effectiveness and validity using samples, and measures ambiguity with Fleiss’ κ.

3.3 Experiments

Experiments evaluate crowd-powered joins through batching, worker aggregation, latency, and feature filtering. Batching lowers cost and latency with limited accuracy effects, while feature filtering substantially reduces comparisons but depends on reliable, discriminative features.

Join Implementations: Batching caused only minor true-positive losses under QualityAdjust, while true-negative rates were not significantly affected.Across batching schemes, QualityAdjust incurred 1–5 additional false negatives; Smart 2x2 performed as well as Simple Join.
Join Implementations: QualityAdjust improved true-positive quality over MajorityVote on batched schemes, which were more attractive to quickly and inaccurately completing workers.Individual trials were more vulnerable to a small number of spammers, producing higher accuracy variance.
Join Implementations: 93% was MajorityVote’s true-positive rate in Simple experiments, exceeding the 78% expected rate for an average worker; QualityAdjust performed significantly better in all cases.The comparison uses the expected single-worker rate of 235/300 = 78%.
Join Implementations: Batching reduced join cost proportionally to batch size, from $135.00 for a naive join to around $13.50 with 3x3 batching.The calculation assumes 900 comparisons, ten assignments per pair, and $0.015 per assignment.
Join Implementations: Batched joins reduced latency despite posting fewer HITs with more work per HIT, although SimpleJoin trials were slower and MTurk latency was difficult to predict.Completion times were evaluated at the 50th, 95th, and 100th assignment percentiles.
Feature Filtering: Feature filtering reduced total join cost by more than a factor of two, while combining features reduced both cost and error rate.Without feature filters, the reported cost was $67.50 for five assignments per HIT.
Feature Filtering: Omitting features reduced filtering error, with gender the most effective filter and hair color responsible for all filtering errors across trials.Feature usefulness depends on whether it guarantees non-matches and whether workers agree on its value.
Feature Filtering: Early κ estimates from 25% random celebrity samples were near full-trial values, supporting Qurk’s use of κ to identify ambiguous filters such as hair color.Workers generally agreed on gender more than hair color, while κ was proposed for automatically excluding unsuitable filters.

3.4 Summary

Qurk combines feature filtering, batching, and quality adjustment to reduce crowd-join cost while preserving result quality. For the celebrity join, these techniques reduce cost from $67.50 to $2.70.

Batching reduces join cost by an order of magnitude with small effects on result quality and latency.Naive and smart batching perform similarly; smart 2x2 batching with QualityAdjust achieves the best accuracy.
Feature filtering reduces the celebrity join cost from $67.50 to $27.00 before batching is applied.
Adding batching to feature filtering reduces the final celebrity-join cost to $2.70, up to a factor of ten further reduction.

4. SORT OPERATOR

Qurk supports crowd-powered sorting through pairwise comparisons, numerical ratings, and a hybrid that refines ratings with targeted comparisons. Agreement metrics identify ambiguous workloads and guide method selection, while window-based refinement improves accuracy efficiently.

Sort interfaces: Qurk sorts by either comparing item groups or averaging numerical ratings, with comparison-based and rating-based methods requiring different HIT complexities.Ratings require O(N) HITs, while comparison-based sorting has quadratic task requirements before batching.
Comparison-based sorting: Worker disagreement can create cycles in pairwise orderings, so Qurk uses graph-based cycle breaking and topological sorting rather than relying on transitivity.Ambiguous worker judgments can make algorithms such as Quicksort yield unpredictable results.
Comparison-based sorting: Grouping S items in one task reduces comparison HITs, and batching b groups reduces HIT count by a factor of b.
Rating-based sorting: Ratings require O(N) HITs and are cheaper, but independently rated items may produce inconsistent pairwise ordering relative to direct comparisons.
Query ambiguity: κ decreases as query ambiguity increases, while τ measures agreement between rating-based and comparison-based orderings.Sampling 10 elements estimates both metrics, enabling method selection or stopping when the dataset is too ambiguous.
Query ambiguity: Rate agrees reasonably with Compare for Q1–Q3 and may be preferable because it is cheaper, whereas Q4 favors Compare because τ is significantly lower.
Hybrid approach: Window 6 achieves τ > .95 in under 30 additional HITs and reaches τ = 1 in half the HITs required by Compare.Window-based refinement moves items toward correct positions more systematically than random or confidence-based selection.
Hybrid approach: The hybrid window-based scheme improves animal-size sorting from τ = .76 to .90 within 20 iterations.

4.3 Summary

Qurk presents rating-based and comparison-based sort operators, then uses agreement metrics to identify ambiguity and choose between them. A hybrid window-based approach achieves comparison-like accuracy at less than one-third the cost.

Qurk implements rating-based sorting with linear complexity and comparison-based sorting with quadratic complexity.
Batching reduces the complexity of sort tasks in both interfaces, while ratings are significantly cheaper but produce orders close to, rather than as good as, comparisons.
τ and modified κ identify when a sort is too ambiguous and when ratings perform comparably to direct comparisons.
The hybrid window-based approach reaches τ > .95 accuracy at less than one-third the cost of comparison-based sorting.

5. END TO END QUERY

The end-to-end query joins movie frames with actor photos, filters and matches scenes using crowd UDFs, and ranks qualifying frames by image quality. Optimizations reduce HITs substantially, while accuracy varies across operators.

Query and operators: The query joins actor photos with movie frames, retains scenes where the actor is the main focus, and orders them by flattering quality.It uses three crowd-based UDFs: numInScene, inScene, and quality.
Query and operators: numInScene filters scenes by asking workers to classify the number of people present, reducing images passed to the join.The available categories are 0, 1, 2, 3+, and UNKNOWN.
Experimental setup: The evaluation extracts 211 movie stills, one second apart from a three-minute movie, and combines them with actor profile photos collected from the Web.The experiment varies filter, join, and sort implementations, including batched and rating-based interfaces.
Results: 1116 HITs are required by a naive unfiltered join with comparisons, versus 77 HITs after applying the optimizations.The authors also report that Smart Join with a 5×5 grid was practical for workers.
Results: The filter produced no errors against manual evaluation, the join had a small number of consistent false positives, and scene-quality ratings showed high variance.The filter’s selectivity was 55%, making its cost outweigh its benefit in this experiment.

6. DISCUSSION AND FUTURE WORK

The discussion highlights operational lessons for running crowd workflows, especially around reputation, batching, worker selection, and scalability. It also identifies limitations and future work in adaptive batching, quality control, and large-scale execution.

Operational lessons: Requester reputation and communication affect relationships with Turkers, while worker feedback can signal whether task pricing is appropriate.Turkers share information about requesters and may request exclusive access when work is overpaid.
Operational lessons: Batching can reduce sort and join costs, but overly large batches may cause workers to refuse tasks and leave assignments incomplete.The authors suggest learning starting batch sizes for different media types and exploring adaptive estimation.
Worker selection: Quality-aware worker selection performs better than simple majority vote for combining assignments and identifying spam-producing workers.The authors did not ban poor workers during experiments, but suggest doing so operationally to reduce future costs.
Future work: Quality assurance is limited because the described method is designed for categorical data, leaving ordinal and interval data as future work.This restricts direct reuse of the method for non-categorical worker responses.
Future work: Scaling datasets by one or two additional orders of magnitude would make join and sort costs prohibitive because both tasks have quadratic complexity.The authors propose combining human computation with machine learning to reserve human effort for harder cases.

7. RELATED WORK

Related systems established declarative approaches and basic architectures for crowdsourced databases, while other frameworks supported iterative task construction or large-scale decomposition. Prior work also informed worker-quality handling and experiment design.

Crowdsourced databases: CrowdDB introduced a declarative interface with crowd-oriented join, sort, and generative-query operators, but did not detail implementation alternatives or performance tradeoffs.The paper positions its work as studying those alternatives and tradeoffs.
Task-programming systems: TurKit supports iterative development of MTurk applications by caching HIT results between program runs.It is described as both a system and a programming model.
Task-programming systems: CrowdForge provides a MapReduce-style model for decomposing large tasks and verifying their results.It represents work outside the database community focused on task posting and decomposition.
Worker quality: Worker-quality methods include gold-standard testing, majority vote, and expectation maximization that estimates worker and result quality without gold-standard data.The authors use an extension that accounts for worker bias on categorical data to improve join results.
Experiment design: Prior evidence that higher wages increase task quantity but not accuracy motivated experiments targeting fewer HITs while maintaining accuracy and per-HIT cost.The cited study held task difficulty fixed when assessing accuracy.

8. CONCLUSION

The paper presents Qurk, a declarative database system that executes joins and sorts with human workers. Its interfaces and optimizations reduce crowd-query cost while preserving accuracy across the reported datasets.

System and contributions: Qurk executes database joins and sorts over human-processed records through a declarative interface running on crowdsourcing platforms such as MTurk.The system combines crowd-based processing with database query execution.
Join processing: Batching interfaces reduce the total number of HITs needed for joins by an order of magnitude.The join interfaces include simple, naive batching, and smart batching.
Join processing: Feature filtering pre-filters join inputs to avoid cross products, and Qurk can automatically select the best features.This optimization targets the cost of crowd-based join processing.
Sorting: Rating often performs comparably to pairwise comparisons for sorting while using far fewer HITs.The paper also presents signals κ and τ for assessing sortability and rating performance.
Sorting: A hybrid sorting scheme combines rating and comparison to improve accuracy over rating while using fewer HITs than comparison.The authors report substantial query-cost reductions without sacrificing accuracy on several real-world datasets.