Human-powered Sorts and Joins

By Adam Marcus, Eugene Wu, David R Karger, Samuel Madden, Rob Miller. Proceedings of the VLDB Endowment, 2011

321 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications

View Paper: https://www.semanticscholar.org/paper/a4b9dcd53e4f698db43d70168873a4a461b943cd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

Truth Inference in Crowdsourcing: Is the Problem Solved? (2017, unknown): “Several crowdsourced databases (e.g., CrowdDB [20], Deco [39], Qurk [37]) are built to incorporate the crowd into query processing, and there are many studies on implementing crowdsourced operators, e.g., Join [50, 36, 52, 11], Max [47, 22], Top-k [14, 55], Group-by [14], etc. Due to the openness of”
Deep entity matching with pre-trained language models (2020, background): “EM solutions have tackled the blocking problem [2, 6, 14, 28, 45] and the matching problem with rules [9, 13, 38, 44], crowdsourcing [16, 18, 43], or machine learning [37, 8, 3, 16, 20].”
Crowdsourced Data Management: A Survey (2016, unknown): “EM-Based methods [15], [41], [58], [70], [79], [100], [104], [112], [118], [127], [139].”
ZenCrowd: leveraging probabilistic reasoning and crowdsourcing techniques for large-scale entity linking (2012, unknown): “Crowdsourcing can also be used for basic computational operations such as sort and join [25].”
Counting with the Crowd (2012, methodology): “The majority of the work in the space has been around database operators, including ﬁlters [18], sorts and joins [17], and max-ﬁnding [12].”
Challenges in Data Crowdsourcing (2016, background): “(Of course, as research in this area [13], [23], [32], [53], [57] suggests, there are much better ways to solve these problems, avoiding many of the unnecessary comparisons, while coping with human errors efficiently.)”
CrowdER: Crowdsourcing Entity Resolution (2012, methodology): “For a table with n records, the naive execution method will lead to O ( n 2 ) HITs. et al In a recently published paper [19], Marcus . proposed two batching strategies to reduce the number of HITs for matching operations (they focused on join operations).”
Artificial Intelligence and Collective Intelligence (2014, background): “One could use comparison between items or ask workers to rate an item on a numerical scale (Marcus et al. 2011).”
Corleone: hands-off crowdsourcing for entity matching (2014, methodology): “Many other works crowdsource joins [19], find the maximal value [11], collect data [28], match schemas [21], and perform data mining [1] and analytics [18].”
Mobile Crowd Sensing and Computing (2015, background): “On one hand, crowdsourcing applications derive values by letting participants perform tasks that request a certain level of human cognition and cannot be mimicked by computers [Marcus et al. 2011].”
Comprehensive and reliable crowd assessment algorithms (2014, background): “B) We present experimental results on synthetic data (Section IV-B) and 3 real datasets (Section IV-C) to study the performance of our confidence intervals on k-ary tasks.”
Crowdsourced Data Management: Industry and Academic Perspectives (2015, methodology): “To accomplish this, we contrast the design choices of two papers on filtering [143] and sorting [132], referring to other papers where it is helpful.”
Foundations of Crowd Data Sourcing (2015, unknown): “, [3, 6, 7, 9, 12, 13, 14, 15, 17, 19, 24, 26, 28].”
CrowdScreen: algorithms for filtering data with humans (2012, background): “Indeed, almost every crowdsourcing application performs some form of filtering [6, 8, 10, 12, 13, 20, 26].”
Scaling Up Crowd-Sourcing to Very Large Datasets: A Case for Active Learning (2014, methodology): “ese systems [17, 19, 24, 25, 33] use optimization techniques to reduce the number of unnecessary questions asked to humans (e.”