Human-powered Sorts and Joins

1 . Human-powered Sorts and Joins Adam Marcus Eugene Wu David Karger Samuel Madden Robert Miller {marcua,sirrice,karger,madden,rcm}@csail.mit.edu ABSTRACT There are several reasons that systems like MTurk are of interest Crowdsourcing marketplaces like Amazon’s Mechanical Turk (MTurk) database researchers. First, MTurk workflow developers often imple- make it possible to task people with small jobs, such as labeling im- ment tasks that involve familiar database operations such as filtering, ages or looking up phone numbers, via a programmatic interface. sorting, and joining datasets. For example, it is common for MTurk MTurk tasks for processing datasets with humans are currently de- workflows to filter datasets to find images or audio on a specific sub- signed with significant reimplementation of common workflows and ject, or rank such data based on workers’ subjective opinion. Pro- ad-hoc selection of parameters such as price to pay per task. We de- grammers currently waste considerable effort re-implementing these scribe how we have integrated crowds into a declarative workflow operations because reusable implementations do not exist. Further- engine called Qurk to reduce the burden on workflow designers. In more, existing database implementations of these operators cannot this paper, we focus on how to use humans to compare items for sort- be reused, because they are not designed to execute and optimize ing and joining data, two of the most common operations in DBMSs. over crowd workers. We describe our basic query interface and the user interface of the A second opportunity for database researchers is in query opti- tasks we post to MTurk. We also propose a number of optimiza- mization. Human workers periodically introduce mistakes, require tions, including task batching, replacing pairwise comparisons with compensation or incentives for work, and take longer than traditional numerical ratings, and pre-filtering tables before joining them, which silicon-based operators. Currently, workflow designers perform ad- dramatically reduce the overall cost of running sorts and joins on the hoc parameter tuning when deciding how many assignments of each crowd. In an experiment joining two sets of images, we reduce the HIT to post in order to increase answer confidence, how much to pay overall cost from $67 in a naive implementation to about $3, without for each task, and how to combine several human-powered operators substantially affecting accuracy or latency. In an end-to-end experi- (e.g., multiple filters) together into a single HIT. These parameters ment, we reduced cost by a factor of 14.5. are amenable to cost-based optimization, and introduce an exciting new landscape for query optimization and execution research. To address these opportunities, we have built Qurk [11], a declar- 1. INTRODUCTION ative query processing system designed to run queries over a crowd Crowd-sourced marketplaces, like Amazon’s Mechanical Turk (MTurk), of workers, with crowd-based filter, join, and sort operators that op- make it possible to recruit large numbers of people to complete small timize for some of the parameters described above. Qurk’s executor tasks that are difficult for computers to do, such as transcribing an au- can choose the best implementation or user interface for different op- dio snippet or finding a person’s phone number on the Internet. Em- erators depending on the type of question or properties of the data. ployers submit jobs (Human Intelligence Tasks, or HITs in MTurk The executor combines human computation and traditional relational parlance) as HTML forms requesting some information or input from processing (e.g., filtering images by date before presenting them to workers. Workers (called Turkers on MTurk) perform the tasks, in- the crowd). Qurk’s declarative interface enables platform indepen- put their answers, and receive a small payment (specified by the em- dence with respect to the crowd providing work. Finally, Qurk au- ployer) in return (typically 1–5 cents). tomatically translates queries into HITs and collects the answers in These marketplaces are increasingly widely used. Crowdflower, a tabular form as they are completed by workers. startup company that builds tools to help companies use MTurk and Several other groups, including Berkeley [5] and Stanford [13] other crowdsourcing platforms now claims to more than 1 million have also proposed crowd-oriented database systems motivated by tasks per day to more than 1 million workers and has raised $17M+ in the advantages of a declarative approach. These initial proposals, in- venture capital. CastingWords, a transcription service, uses MTurk to cluding our own [11], presented basic system architectures and data automate audio transcription tasks. Novel academic projects include models, and described some of the challenges of building such a a word processor with crowdsourced editors [1] and a mobile phone crowd-sourced database. The proposals, however, did not explore the application that enables crowd workers to identify items in images variety of possible implementations of relational operators as tasks taken by blind users [2]. on a crowd such as MTurk. In this paper, we focus on the implementation of two of the most Permission to make digital or hard copies of all or part of this work for important database operators, joins and sorts, in Qurk. We believe we personal or classroom use is granted without fee provided that copies are are the first to systematically study the implementation of these op- not made or distributed for profit or commercial advantage and that copies erators in a crowdsourced database. The human-powered versions of bear this notice and the full citation on the first page. To copy otherwise, to these operators are important because they appear everywhere. For republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Articles from this volume were invited to present example, information integration and deduplication can be stated as their results at The 38th International Conference on Very Large Data Bases, a join between two datasets, one with canonical identifiers for enti- August 27th - 31st 2012, Istanbul, Turkey. ties, and the other with alternate identifiers. Human-powered sorts Proceedings of the VLDB Endowment, Vol. 5, No. 0 are widespread as well. Each time a user provides a rating, product Copyright 2011 VLDB Endowment 2150-8097/11/07... $ 10.00. 

2 .review, or votes on a user-generated content website, they are con- The basic data model is relational, with user-defined scalar and tributing to a human-powered ORDER BY. table functions (UDFs) used to retrieve data from the crowd. Rather Sorts and joins are challenging to implement because there are a than requiring users to implement these UDFs in terms of raw HTML variety of ways they can be implemented as HITs. For example, to forms or low-level declarative code, most UDFs are implemented us- order a list of images, we might ask users to compare groups of im- ing one of several pre-defined Task templates that specify informa- ages. Alternatively, we might ask users for numerical ratings for each tion about how Qurk should present questions to the crowd. image. We would then use the comparisons or scores to compute the To illustrate a simple example, suppose we have a table of celebri- order. The interfaces for sorting are quite different, require a differ- ties, with schema celeb(name text, img url). ent number of total HITs and result in different answers. Similarly, We want the crowd to filter this table and find celebrities that are we explore a variety of ways to issue HITs that compare objects for female. We would write: computing a join, and study answer quality generated by different interfaces on a range of datasets. SELECT c.name Besides describing these implementation alternatives, we also ex- FROM celeb AS c plore optimizations to compute a result in a smaller number of HITs, WHERE isFemale(c) which reduces query cost and sometimes latency. Specifically, we look at: With isFemale defined as follows: • Batching: We can issue HITs that ask users to process a vari- TASK isFemale(field) TYPE Filter: able number of records. Larger batches reduce the number of Prompt: "<table><tr> \ HITs, but may negatively impact answer quality or latency. <td><img src=’%s’></td> \ • Worker agreement: Workers make mistakes, disagree, and at- <td>Is the person in the image a woman?</td> \ tempt to game the marketplace by doing a minimal amount </tr></table>", tuple[field] YesText: "Yes" of work. We evaluate several metrics to compute answer and NoText: "No" worker quality, and inter-worker agreement. Combiner: MajorityVote • Join pre-filtering: There are often preconditions that must be true before two items can be joined. For example, two people Tasks have types, which define the low-level implementation and are different if they have different genders. We introduce a way interface that is generated. For the case of a Filter task, it takes tuples for users to specify such filters, which require a linear pass by as input, and produces tuples that users indicate satisfy the question the crowd over each table being joined, but allow us to avoid a specified in the Prompt field. Here, Prompt is simply an HTML full cross-product when computing the join. block into which the programmer can substitute fields from the tuple • Hybrid sort: When sorting, asking users to rate items requires being filtered. This tuple is available via the tuple variable; its fewer tasks than directly comparing pairs of objects, but pro- fields are accessed via the use of field names in square brackets ([]). duces a less thorough ordering. We introduce a hybrid algo- In this case, the question shows an image of the celebrity and asks rithm that uses rating to roughly order items, and iteratively if the person is female. The YesText and NoText fields are used improves that ordering by using comparisons to improve the to allow developers to specify the titles of buttons for the answers to order of objects with similar ratings. questions. Our join optimizations result in more than an order-of-magnitude Since workers make mistakes, generate unusual answers, or at- (from $67 to $3 on a join of photos) cost reduction while maintaining tempt to game the system by performing tasks without thinking to result accuracy and latency. For sorts, we show that ranking (which get paid quickly, it is often valuable to ask multiple workers for an- requires a number of HITs linear in the input size) costs dramatically swers. We allow users to specify how many responses are desired. less than ordering (which requires a number of HITs quadratic in the By default we send jobs to 5 workers. Users can specify if they want input size), and produces comparable results in many cases. Finally, more workers to answer, and in our experiments we measure the ef- in an end-to-end test, we show that our optimizations can reduce by fect of this value on answer quality. We also explore algorithms for a factor of 14 the number of HITs required to join images of actors adaptively deciding whether another answer is needed in Section 6. and rank-order them. The Combiner field specifies a function that is used to specify In addition to describing these specific operators and optimiza- how to combine multiple responses into a single answer. In addi- tions, we review the design of Qurk (originally described in our tion to providing a MajorityVote combiner, which returns the CIDR paper [11]) and present several extensions to our basic system most popular answer, we have implemented the method described by model that we have developed as we implemented the system. Ipeirotis et al. [6]. This method, which we call QualityAdjust, identifies spammers and worker bias, and iteratively adjusts answer confidence accordingly in an Expectation Maximization-like fashion. 2. LANGUAGE OVERVIEW AND SYSTEM Filters describe how to ask a worker about one tuple. The query In this section, we describe the query language and implementa- compiler and optimizer can choose to repeat the Prompts for several tion of Qurk. An initial version of this design appeared in a short batched tuples at one time. This allows workers to perform several paper [11], though the design has since been refined. filter operations on records from the same table in a single HIT. Advanced users of Qurk can define their own tasks that, for exam- 2.1 Data Model and Query Language ple, generate specialized UIs. However, these custom UIs require ad- This section describes the Qurk data model and query language, ditional effort if one wishes to take advantage of optimizations such and focuses on how joins and sorts are expressed through a series as batching. of queries. Our examples have workers provide us with information about various images. We use image examples for consistency of ex- 2.2 Generative Tasks planation, and because databases typically do not perform processing Filter tasks have a constrained user interface for providing a re- over images. Qurk’s use cases are not limited to processing images. sponse. Often, a task requires workers to generate unconstrained Franklin et al. [5] show how human computation-aware joins can be input, such as producing a label for an image or finding a phone used for entity disambiguation, and we explore using workers to rate number. In these situations, we must normalize worker responses to a video in Section 5. better take advantage of multiple worker responses. Since generative 

3 .tasks can have workers generate data for multiple fields and return This Rank UDF can also be used to implement top-K (via a LIMIT tuples, this is a way to generate tables of data. clause) and MAX/MIN aggregates. For top-K, we simply perform a For example, say we have a table of animal photos: complete sort and extract the top-K items. For MAX/MIN, we use animals(id integer, img url) an interface that extracts the best element from a batch at a time. and we wish to ask workers to provide us with the common name and species of each animal: 2.4 Joins and Feature Extraction The basic implementation of joins is quite similar to that for sorts SELECT id, animalInfo(img).common, and filters. For example, suppose we want to join table of images animalInfo(img).species with schema photos(img url) with the celebrities table defined FROM animals AS a above: In this case, animalInfo is a generative UDF which returns SELECT c.name two fields, common with the common name, and species with the FROM celeb c JOIN photos p ON samePerson(c.img,p.img) species name. The samePerson predicate is an equijoin task, as follows: TASK animalInfo(field) TYPE Generative: Prompt: "<table><tr> \ TASK samePerson(f1, f2) TYPE EquiJoin: <td><img src=’%s’> \ SingluarName: "celebrity" <td>What is the common name \ PluralName: "celebrities" and species of this animal? \ LeftPreview: "<img src=’%s’ class=smImg>",tuple1[f1] </table>", tuple[field] LeftNormal: "<img src=’%s’ class=lgImg>",tuple1[f1] Fields: { RightPreview: "<img src=’%s’ class=smImg>",tuple2[f2] common: { Response: Text("Common name") RightNormal: "<img src=’%s’ class=lgImg>",tuple2[f2] Combiner: MajorityVote, Combiner: MajorityVote Normalizer: LowercaseSingleSpace }, species: { Response: Text("Species"), The fields in this task are used to generate one of several different Combiner: MajorityVote, join interfaces that is presented to the user. The basic idea with these Normalizer: LowercaseSingleSpace } } interfaces is to ask users to compare pairs of elements from the two tables (accessed through the tuple1 and tuple2 variables); these A generative task provides a Prompt for asking a question, much pairs are used to generate join results. As with sorting and filter, Qurk like a filter task. It can return a tuple with fields specified in the can automatically batch together several join tasks into one HIT. A Fields parameter. Just like the filter task, we can combine the sample interface is shown in Figure 2a. work with a Combiner. We also introduce a Normalizer, which Feature Extraction: As we discuss in Section 3.2, we often wish takes the text input from workers and normalizes it by lower-casing to extract features of items being joined together to filter potential and single-spacing it, which makes the combiner more effective at join candidates down, and allow us to avoid computing a cross prod- aggregating responses. uct. Some features may not be useful for accurately trimming the cross product, and so we introduce a syntax for users to suggest fea- 2.3 Sorts tures for filtering that may or may not be used (as we discuss in Sec- Sorts are implemented through UDFs specified in the ORDER tion 3.2, the system automatically selects which features to apply.) BY clause. Suppose, for example, we have a table of images of We supplement traditional join syntax with a POSSIBLY keyword squares of different sizes, with schema squares(label text, that indicates the features that may help filter the join. For example, img url). the query: To order these by the area of the square, we write: SELECT c.name FROM celeb c JOIN photos p SELECT squares.label ON samePerson(c.img,p.img) FROM squares AND POSSIBLY gender(c.img) = gender(p.img) ORDER BY squareSorter(img) AND POSSIBLY hairColor(c.img) = hairColor(p.img) AND POSSIBLY skinColor(c.img) = skinColor(p.img) where the task definition for squareSorter is as follows. joins the celeb and photos table as above. The additional TASK squareSorter(field) TYPE Rank: SingularName: "square" POSSIBLY clause filters extract gender, hair color, and skin color PluralName: "squares" from images being joined and are used to reduce the number of join OrderDimensionName: "area" candidates that the join considers. Specifically, the system only asks LeastName: "smallest" users to join elements from the two tables if all of the predicates in MostName: "largest" the POSSIBLY clause it tries are satisfied (it may not try all predi- Html: "<img src=’%s’ class=lgImg>",tuple[field] cates.) These predicates can be applied in a linear scan of the tables, avoiding a cross product that might otherwise result. Here, gender, As we discuss in Section 4, Qurk uses one of several different in- hairColor, and skinColor are UDFs that return one of sev- terfaces for ordering elements. One version asks users to order small eral possible values (rather than table functions as with the previous subsets of elements; the other version asks users to provide a numer- UDFs.) For example: ical ranking for each element. The Rank task asks the developer to specify a set of labels that are used to populate these different inter- TASK gender(field) TYPE Generative: faces. In the case of comparing several squares, the above text will Prompt: "<table><tr> \ generate an interface like the one shown in Figure 5. <td><img src=’%s’> \ <td>What this person’s gender? \ As with filters, tasks like Rank specified in the ORDER BY clause </table>", tuple[field] can ask users to provide ordering information about several records Response: Radio("Gender", from the input relation in a single HIT. This is allows our interface to ["Male","Female",UNKNOWN]) batch together several tuples for a worker to process. Combiner: MajorityVote 

4 . !"#$%&& L+/$& sends tasks to the Task Manager. Qurk is implemented as a Scala G/+#A(+& 0#/$5/+& workflow engine with several types of input including relational databases >?"&$/+#A(+& and tab-delimited text files. We created several interface prototypes @9435A/B& and experiments in Python using the Django web framework. '()*+*,+&!)-)./$& 0#/$1&23*456/$& Pricing Tasks: Our current Qurk implementation runs on top of >?"+& Mechanical Turk. We pay a fixed value per HIT ($0.01 in our exper- >?"&@9435A/$& G/+#A(+& G/+#A(+& iments). Research by Mason and Watts has suggested that workers ")+%C& )H& )I& JH& on Mechanical Turk do not do particularly higher quality work for ")+%&!9B/A& ")+%D& ")+%E& < 5-=& 5-;& higher priced tasks [12]. Mason and Watts also find that workers in- ?-(/$-)A&& crease the amount of work they perform with an increase in wage, ")+%&@),K/& >?"& ")+%& ")+%+& = ; suggesting that Turkers have an internal model of how much money !)-)./$& 78/,#(9$& their work is worth. In all of our experiments, the basic tasks we per- form are quick enough that users will do several of them for $0.01, ')F/B&G/+#A(+& ?-3#(&:)()& which means we can batch together several tasks into a single HIT. Paying more per HIT would allow us to perform more batching, but :;& the degree of additional batching would scale linearly with the addi- tional money we pay, which wouldn’t save us money. 1: The Qurk system architecture. Objective Function: Because we pay a fixed value per HIT, our system currently uses a simple objective function: minimize the to- In contrast to the animalInfo generative task, note that this tal number of HITs required to fully process a query subject to the generative task only has one field, so it omits the Fields parame- constraint that query answers are actually produced1 . The constraint ter. Additionally, the field does not require a Normalizer because arises because certain optimizations we apply, like batching, will it has a constrained input space. eventually lead to HITs that are too time-consuming for users to be It is possible for feature extraction interfaces to generate a special willing to do for $0.01. value UNKNOWN, which indicates a worker could not tell its value. Batching: Our system automatically applies two types of batching This special value is equal to any other value, so that an UNKNOWN to tasks: merging, where we generate a single HIT that applies a value does not remove potential join candidates. given task (operator) to multiple tuples, and combining, where we generate a single HIT that applies several tasks (generally only filters 2.5 HIT Generation and generative tasks) to the same tuple. Both of these optimizations The above queries need to be translated into HITs that are issued have the effect of reducing the total number of HITs2 . We discuss to the underlying crowd. It’s important to generate tasks in a way that our approach to batching sorts and joins in more detail in the next keeps the total number of HITs generated down. For example, as in two sections; for filters and generative tasks, batches are generated a traditional database, it’s better to filter tables before joining them. by concatenating the HTML forms for multiple tasks together onto Query planning in Qurk is done in a way similar to conventional log- the single web page presented to the user. ical to physical query plan generation; a query is translated into a HIT Groups: In addition to batching several tasks into a sin- plan-tree that processes input tables in a bottom-up fashion. Rela- gle HIT, our system groups together (batched) HITs from the same tional operations that can be performed by a computer rather than operator into groups that are sent to Mechanical Turk as a single humans are pushed down the query plan as far as possible (including HIT group. This is done because Turkers tend to gravitate toward pushing non-HIT joins below HIT-based filters when possible.) HIT groups with more tasks available in them, as they can more The system generates HITs for all non-join WHERE clause ex- quickly perform work once they are familiar with the interface. In pressions first, and then as those expressions produce results, feeds CrowdDB [5], the authors show the effect of HIT group size on task them into join operators, which in turn produce HITs that are fed to completion rate. successive operators. As with traditional query execution, HITs for Now that we’ve presented our general architecture, we describe the conjuncts (ANDs) of filters are issued serially, while disjuncts (ORs) specific implementations and optimizations we developed for joins are issued in parallel. After filters, joins are executed left-deep, with and sorts. results of lower joins being pipelined into higher joins. Qurk cur- rently lacks selectivity estimation, so it orders filters and joins as they appear in the query. 3. JOIN OPERATOR This section describes several implementations of the join opera- 2.6 Architecture and Implementation tor, and the details of our feature filtering approach for reducing join In this section, we briefly describe the architecture of Qurk and complexity. We present a series of experiments to show the quality provide a few details about its implementation. and performance of different join approaches. The basic architecture is shown in Figure 1. Queries are issued through the Query Optimizer, which generates a logical plan and be- 3.1 Implementation gins executing it in the Executor. The executor runs the plan, gener- ating tasks according to the rules in Section 2.5. These tasks are sent 1 Other possible objective functions include maximizing answer to the Task Manager, which applies batching and other optimizations quality or minimizing answer latency. Unfortunately, answer quality and dispatches them to the Task Cache/Model/HIT Compiler, which is hard to define (especially since the correct answer to many human first checks to see if the HIT is cached and if not generates HTML for computation tasks cannot be known), and latency is highly variable, the HIT and dispatches it to the crowd. As answers come back, they and probably better optimized through low-level optimizations like those used in quikTurkit [2]. are cached, extracted from their HTML forms, and fed to the execu- 2 For sequences of conjunctive predicates, combining actually does tor, which sends the results to the operators that operate on them (or more “work” on people than not combining, since tuples that may to the user). These operators in turn generate more tasks. have been discarded by the first filter are run through the second filter In our implementation, each operator runs in its own thread, asyn- as well. Still, as long as the first filter does not have 0 selectivity, this chronously consumes results from input queues, and autonomously will reduce the total number of HITs that have to be run. 

5 . The join HIT interface asks a worker to compare elements from cross product. This clause allows the developer to specify that some two joined relations. Qurk implements a block nested loop join, and features must be true for the join predicate to evaluate to true. For uses the results of the HIT comparisons to evaluate whether two ele- example, two profile images shouldn’t join unless they have the same ments satisfy the join condition. We do not implement more efficient gender, hair color, and skin color. These predicates allow us to only join algorithms (e.g., hash join or sort-merge join) because we do not consider join pairs which match the extracted features. have a way to compute item (e.g., picture) hashes for hash joins or We now explain the benefit of this filtering. To simplify our anal- item order for sort-merge joins. ysis, we assume that all filter features are uncorrelated, and that the The following screenshots and descriptions center around evalu- filters do not emit the value UNKNOWN. ating join predicates on images, but are not limited to image data Suppose there are N POSSIBLY clauses added to a join. Let types. The implementations generalize to any field type that can be F = {F1 , ..., FN }, where Fi is a set that contains the possible values displayed in HTML. In this section, we assume the two tables being for the feature being compared in POSSIBLY clause i. For example, joined are R and S, with cardinalities |R| and |S|, respectively. if the ith feature is hairColor, Fi = {black, brown, blond, white}. Let the probability that feature i (e.g., hair color) has value j (e.g., 3.1.1 Simple Join brown) in table X to be ρXij . Then, for two tables, R and S, the Figure 2a shows an example of a simple join predicate interface probability that those two tables match on feature i is: called SimpleJoin. In this interface, a single pair of items to be joined X is displayed in each HIT along with the join predicate question, and σi = ρSij × ρRij two buttons (Yes, No) for whether the predicate evaluates to true or j∈Fi false. This simplest form of a join between tables R and S requires In other words, σi is the selectivity of feature i. Thus, the selectivity |R||S| HITs to be evaluated. of all expressions in the POSSIBLY clause (assuming the features are independent) is: 3.1.2 Naive Batching Y Figure 2b shows the simplest form of join batching, called Naive- Sel = σi Batch. In NaiveBatch, we display several pairs vertically. Yes, No i∈[1...N ] radio buttons are shown with each pair that is displayed. A Submit Feature filtering causes the total number of join HITs that are exe- button at the bottom of the interface allows the worker to submit all cuted to be a fraction Sel of what would be executed by a join al- of the pairs evaluated in the HIT. If the worker clicks Submit with- gorithm alone. This benefit comes at the cost of running one linear out having selected one of Yes or No for each pair, they are asked to pass over each table for each feature filter. Of course, the HITs in the select an option for each unselected pair. linear pass can be batched through merging and combining. For a batch size of b, where b pairs are displayed in each HIT, we In general, feature filtering is helpful, but there are three possible can reduce the number of HITs to |R||S| b . cases where we may not want to apply a filter: 1) if the additional cost of applying the filter does not justify the reduction in selectivity 3.1.3 Smart Batching it offers (e.g., if all of the people in two join tables of images have Figure 2c shows a more complex join batching interface called brown hair); 2) if the feature doesn’t actually guarantee that two en- SmartBatch. Two columns of images are displayed, and workers are tities will not join (e.g., because a person has different hair color in asked to click on pairs of images that match the join predicate. The two different images); or 3) if the feature is ambiguous (i.e., workers first column contains images from table R and the second contains do not agree on its value). images from table S. To detect 1), we run the feature filter on a small sample of the data Once a worker selects a pair, it is displayed in a list to the right of set and estimate selectivity, discarding filters that are not effective. the columns, and can be removed (if added by mistake) by clicking To evaluate 2) for a feature f , we also use a sample of both tables, on the pair. All selected pairs are connected by a line. If none of computing the join result jf − with all feature filters except f , as the images match the join predicate, the worker is asked to click a well as the join result with f , jf + . We then measure the fraction checkbox indicating no matches. In order to submit the HIT, the box |jf − −jf + | must be checked or at least one pair must be selected. |jf − | and if it is below some threshold, we discard that feature To conserve vertical space, images are not displayed at full size. filter clause from the join. If a user hovers over an image, it is displayed at the size used in For case 3) (feature ambiguity), we use a measure called inter-rater SimpleJoin and NaiveJoin (e.g., in Figure 2c, the mouse is hovering reliability (IRR), which measures the extent to which workers agree. over Notorious B.I.G, who is displayed at full size). As a quantitative measure of IRR, we utilize Fleiss’ κ [4]. Fleiss’ For r images in the first column and s in the second column, we κ is used for measuring agreement between two or more raters on must evaluate |R||S| rs HITs. labeling a set of records with categorical labels (e.g., true or false). It is a number between -1 and 1, where a higher number indicates 3.1.4 Alternative Join Algorithms greater agreement. A κ of 0 roughly means that the ratings are what There are a number of alternative join algorithms that we do not would be expected if the ratings had been sampled randomly from a consider in this paper. For example, we could first generate HITs that weighted distribution, where the weights for a category are propor- ask workers to label each tuple with a unique identifier of the entity tional to the frequency of that category across all records. For feature that it represents, then perform a traditional join on the identifier. filters, if we measure κ to be below some small positive threshold for The focus of this paper is understanding the accuracy-cost tradeoffs a given filter, we discard it from our filter set. Due to our use of of batching and combining, so these alternatives are outside the scope Fleiss’ κ, Qurk currently only supports detecting ambiguity for cate- of this paper. However, we note that our results can be used to benefit gorical features, although in some cases, range-valued features may other join algorithms, and we use the idea of labeling tuples for our be binned into categories. feature filtering optimization described in Section 3.2. 3.3 Experiments 3.2 Feature Filtering Optimization We now explore the various join implementations and the effects In Section 2.1, we introduced the POSSIBLY clause to joins for of batching and feature filtering. We also explore the quality of identifying feature-based filters that may reduce the size of a join worker output as they perform more tasks. 

6 . (a) Simple Join (b) Naive Batching (c) Smart Batching 2: Three interfaces for the join operator. Elements are resized for readability. Implementation True Pos. True Pos. True Neg True Neg QualityAdjust on all ten assignments per pair are reported with (MV) (QA) (MV) (QA) the prefixes MV and QA, respectively. From these results, it is evi- IDEAL 20 20 380 380 dent that all approaches work fairly well, with at most 1 photo which Simple 19 20 379 376 Naive 19 19 380 379 was not correctly matched (missing true positive). We show in the Smart 20 20 380 379 next section that using QA and MV is better than trusting any one worker’s result. 1: Baseline comparison of three join algorithms with no batching enabled. Each join matches 20 celebrities in two tables, resulting in (" !"#$%&'(&)(*&""+$,(-'./+".( 20 image matches (1 per celebrity) and 380 pairs with non-matching !#'" celebrities. Results reported for ten assignments aggregated from two trials of five assignments each. With no batching enabled, the !#&" algorithms have comparable accuracy. 3.3.1 Dataset !#%" In order to test join implementations and feature filtering, we cre- ated a celebrity join dataset. This dataset contains two tables. The !#$" first is celeb(name text, img url), a table of known celebri- ties, each with a profile photo from IMDB3 . The second table is !" photos(id int, img url), with of images of celebrities col- )*+,-." /012."3" /012."4" /012."(!" )+056" )+056" $7$" 373" lected from People Magazine’s collection of photos from the 2011 859.":;<*=2.<">?@A" 859.":;<*=2.<">BCA" Oscar awards. Each table contains one image of each celebrity, so joining N cor- 859."/.D0=2.<">?@A" 859."/.D0=2.<">BCA" responding rows from each table naively takes N 2 comparisons, and has selectivity N1 . 3: Fraction of correct answers on celebrity join for different batching approaches. Results reported for ten assignments aggregated from 3.3.2 Join Implementations two runs of five assignments each. Joins are conducted on two tables In this section, we study the accuracy, price, and latency of the with 30 celebrities each, resulting in 30 matches (1 per celebrity) and celebrity join query described in Section 2.4. 870 non-matching join pairs. We run each of the join implementations twice (Trial #1 and #2) with five assignments for each comparison. This results in ten com- parisons per pair. For each pair of trials, We ran one trial in the &" morning before 11 AM EST, and one in the evening after 7 PM EST, to measure variance in latency at different times of day. All assign- %#$" !"#$%&'()*+,-( ments are priced at $0.01, which costs $0.015 per assignment due to Amazon’s half-cent HIT commission. %" We use the two methods described in Section 2.1 to combine the join responses from each assignment. For MajorityVote, we !#$" identify a join pair if the number of positive votes outweighs the negative votes. For QualityAdjust, we generate a corpus that !" '()*+," -./0,"%!" -./0,"$" -./0,"1" ').23"141" ').23"&4&" contains each pair’s Yes, No votes along with the Amazon-specified ./0%(1234$2$%#"5/%,( Turker ID for each vote. We execute the algorithm in [6] for five iter- ations on the corpus, and parametrize the algorithm to penalize false $!5" 6$5" %!!5" negatives twice as heavily as false positives. Baseline Join Algorithm Comparison: The first experiment veri- 4: Completion time in hours of the 50th , 95th , and 100th per- fies that the three join implementations achieve similar accuracy in centile assignment for variants of celebrity join on two tables with unbatched form. Table 1 contains the results of the joins of a sample 30 celebrities each. of 20 celebrities and matching photos. The ideal algorithm results in 20 positive matches and 380 negative matches (pairs which do Effect of Batching: In our next experiment, we look at the effect not join). The true positives and negatives for MajorityVote and of batching on join quality and price. We compared our simple al- gorithm to naive batching with 3, 5, and 10 pairs per HIT and smart 3 http://www.imdb.com batching with a 2×2 and 3×3 grid, running a celebrity join between 

7 .two images tables with 30 celebrity photos in each table. The answer Trial # Combined? Errors Saved Comparisons Join Cost quality results are shown in Figure 3. There are several takeaways 1 Y 1 592 $27.52 from this graph. 2 Y 3 623 $25.05 1 N 5 633 $33.15 First, all batching schemes except Smart 2x2, which performs as 2 N 5 646 $32.18 well as the Simple Join, do have some negative effect on the overall total number of true positives. When using QA, the effect is relatively 2: Feature Filtering Effectiveness. minor with 1–5 additional false negatives on each of the batching Omitted Feature Errors Saved Comparisons Join Cost schemes. There is not a significant difference between naive and smart batching. Batching does not significantly affect the overall Gender 1 356 $45.30 Hair Color 0 502 $34.35 true negative rate. Skin Color 1 542 $31.28 Second, QA does better than MV in improving true positive result quality on the batched schemes. This is likely because QA includes 3: Leave-One Out Analysis for the first combined trial. Removing filters for identifying spammers and sloppy workers, and these larger, hair color maintains low cost and avoids false negatives. batched schemes are more attractive to workers that quickly and in- accurately complete the tasks. The overall error rate between individ- ual trials, with 5 assignments per pair, was approximately the same. 3.3.4 Feature Filtering However, individual trials are more vulnerable to a small number of Finally, we ran an experiment to measure the effectiveness of fea- spammers, which results in higher variance in accuracy. ture filtering. In this experiment, we asked workers to choose the Third, MV and QA often achieve far higher accuracy as compared hair color, skin color, and gender of each of the 60 images in our two to the expected accuracy from asking a single worker for each HIT. tables. For each feature, we ran two trials with 5 votes per image in In the Simple experiments, the expected true positive rate of an aver- each trial, combining answers using majority vote. We also ran two age worker was 235/300 = 78%, whereas MV was 93%. MV per- trials with a combined interface where we asked workers to provide formed the worst in the Smart 3x3 experiments, yet still performed all three features at once. as well the expected true positive rate of 158/300 = 53%. In all Table 2 shows the effectiveness of applying all feature filters. We cases, QA performed significantly better. report the number of errors, which is the number of pairs that actu- We also measured the cost (in dollars) of running the complete ally should have joined (out of 30) that didn’t pass all three feature join (900 comparisons) for the two trials (with 10 assignments per filters in the four trials, as well as the saved comparisons, which is pair) at a cost of $0.015 per assignment ($0.01 to the worker, $0.005 the number of comparisons (out of 870) that feature filtering helped to Amazon). The cost of a naive join is thus 900 × $0.015 × 10 = avoid. We also report the total join cost with feature filtering (without $135.00. The cost falls proportionally with the degree of batching feature filters the cost would be $67.50 for 5 assigments per HIT.) (e.g., naive 10 reduces cost by a factor of 10, and a 3x3 join reduces From these results, we can see that feature filters substantially re- cost by a factor of 9), resulting in a cost of around $13.50. duce the overall cost (by more than a factor of two), and that combin- Figure 4 shows end-to-end latency values for the different join im- ing features both reduces cost and error rate. The reason that combin- plementations, broken down by the time for 50%, 95%, and 100% ing reduces error rate is that in the batched interface, workers were percent of the assignments to complete. We observe that a reduction much more likely to get hair color correct than in the non-batched in HITs with batching reduces latency, even though fewer HITs are interface. We hypothesize that this is because when asked about all posted and each HIT contains more work. Both SimpleJoin trials three attributes at once, workers felt that they were doing a simple were slower than all other runs, but the second SimpleJoin trial was demographic survey, while when asked solely any one feature (in particularly slow. This illustrates the difficulty of predicting latency this case hair color), they may have overanalyzed the task and made in a system as dynamic as MTurk. Finally, note that in several cases, more errors. the last 50% of wait time is spent completing the last 5% of tasks. We now look at the error rate, saved comparisons, and total cost This occurs because the small number of remaining tasks are less ap- when we omit one feature from the three. The goal of this analysis is pealing to Turkers looking for long batches of work. Additionally, to understand whether omitting one of these features might improve some Turkers pick up and then abandon tasks, which temporarily join quality by looking at their effectiveness on a small sample of the blocks other Turkers from starting them. data as proposed in Section 3.2. The results from this analysis on the first combined trial are shown in Table 3 (all of the trials had the same result). From this table, we can see that omitting features reduces the error rate, and that gender is by far the most effective feature to filter on. From this result, we conclude that hair color should potentially 3.3.3 Assignments vs. Accuracy be left out. In fact, hair color was responsible for all of the errors in filtering across all trials. One concern is that worker performance will degrade as they exe- To see if we can use inter-rater reliability as a method for deter- cute more tasks and become bored or less cautious. This is particu- mining which attributes are ambiguous, we compute the value of κ larly a concern as our results (and those of CrowdDB [5]) suggest the (as described in Section 3.2) for each of the attributes and trials. The number of tasks completed by each worker is roughly Zipfian, with results are shown in Table 4. From the table, we can see that the a small number of workers completing a large fraction of the work. κ value for gender is quite high, indicating the workers generally To test if the amount of work done by a worker is negatively cor- agree on the gender of photos. The κ value for hair is much lower, related with the quality of his or her work, we performed a linear because many of the celebrities in our photos have dyed hair, and regression on accuracy. For a combination of responses to the two because workers sometimes disagree about blond vs. white hair. Fi- simple 30 × 30 join tasks, we fit the number of tasks each worker did correct tasks ), and found R2 = 0.028 with nally, workers agree more about skin color when it is presented in with their accuracy ( tasks completed the combined interface, perhaps because they may feel uncomfort- p < .05. While accuracy and number of tasks completed are pos- able answering questions about skin color in isolation. itively correlated (the slope, β, is positive), the correlation explains Table 4 displays average and standard deviations of κ for 50 25% less than 3% of the variance in accuracy. This suggests no strong random samples of celebrities in each trial. We see that these κ value effect between work done and accuracy. approximations are near the true κ value in each trial, showing that 

8 .Trial # Sample Size Combined? Gender κ (std) Hair κ (std) Skin κ (std) 1 100% Y 0.93 0.29 0.73 2 100% Y 0.89 0.42 0.95 1 100% N 0.85 0.43 0.45 2 100% N 0.94 0.40 0.47 1 25% Y 0.93 (0.04) 0.26 (0.09) 0.61 (0.37) 2 25% Y 0.89 (0.06) 0.40 (0.11) 0.95 (0.20) 1 25% N 0.85 (0.07) 0.45 (0.10) 0.39 (0.29) 2 25% N 0.93 (0.06) 0.38 (0.08) 0.47 (0.24) 4: Inter-rater agreement values (κ) for features. For each trial, we display κ calculated on the entire trial’s data and on 50 random sam- ples of responses for 25% of celebrities. We report the average and standard deviation for κ from the 50 random samples. (a) Comparison Sort Qurk can use early κ values to accurately estimate worker agreement on features without exploring the entire dataset. From this analysis, we can see that κ is a promising metric for automatically determining that hair color (and possibly skin color) should not be used as a feature filter. 3.4 Summary We found that for joins, batching is an effective technique that has small effect on result quality and latency, offering an order-of- magnitude reduction in overall cost. Naive and smart batching per- form similarly, with smart 2x2 batching and QA achieving the best accuracy. In Section 5 we show an example of a smart batch run where a 5x5 smart batch interface was acceptable, resulting in a 25x (b) Rating Sort cost reduction. We have never seen such large batches work for naive 5: Two interfaces for the order by operator. batching. We found that the QA scheme in [6] significantly improves result quality, particularly when combined with batching, because to build a directed graph of items, where there is an edge from item it effectively filters spammers. Finally, feature filtering offers sig- i to item j if i > j. We can run a cycle-breaking algorithm on the nificant cost savings when a good set of features can be identified. graph, and perform a topological sort to compute an approximate or- Putting these techniques together, we can see that for celebrity join, der. Alternatively, as we do in our implementation, we can compute feature filtering reduces the join cost from $67.50 to $27.00. Adding the number of HITs in which each item was ranked higher than other batching can further reduce the cost by up to a factor of ten, yielding items. This approach, which we call “head-to-head,” provides an in- a final cost for celebrity join of $2.70. tuitively correct ordering on the data, which is identical to the true ordering when there are no cycles. Cycles also mean that we can’t use algorithms like Quicksort that 4. SORT OPERATOR only perform O(N logN ) comparisons, because these algorithms don’t Users often want to perform a crowd-powered sort of a dataset, compare all elements, and yield unpredictable results in ambiguous such as “order these variants of a sentence by quality,” or “order the situations (which we found while running our experiments). images of animals by adult size.” Instead of comparing a single pair at a time, our interface, shown As with joins, the HITs issued by Qurk for sorting do not actually in Figure 5a, displays groups of S items, and asks the worker to implement the sort algorithm, but provide an algorithm with infor- rank items mation it needs by either: 1) comparing pairs of items to each other, ` ´ within a group relative to one-another. The result of each task is S2 pairwise comparisons, which reduces the number of HITs or 2) assigning a rating to each item. The Qurk engine then sorts ×(N −1) to NS×(S−1) . Although the number of HITs is large, they can be items using pairwise comparisons or their ratings. In this section we describe our two basic implementations of these ideas, as well as a executed in parallel. We can batch b such groups in a HIT to reduce hybrid algorithm that combines them. We also compare the accuracy the number of hits by a factor of b. and total number of HITs required for each approach. 4.1.2 Rating-based 4.1 Implementation The second approach is to ask workers to rate each item in the dataset along a numerical scale. We then compute the mean of all 4.1.1 Comparison-based ratings for each item, and sort the dataset using these means. The comparison-based approach (Figure 5a) asks workers to di- Figure 5b illustrates the interface for a single rating task. The rectly specify the ` ´ordering of items in the dataset. The naive ap- worker is shown a single item and asked to rate it along a seven-point proach requires N2 tasks per sort assignment, which is expensive for Likert Scale [9], which is commonly used for subjective survey data. large datasets. While the optimal number of comparisons is O(N logN ) In order to provide context to assign a rating, we show ten randomly for traditional sort algorithms, we now explain why we require more sampled images along the top of the interface. Showing a random comparison tasks. selection allows us to give the worker a sense for the dataset without In practice, because these individual sort HITs are done by differ- knowing its distribution a priori. ent workers, and because tasks themselves may be ambiguous, it can The advantage of this approach are that it only requires O(N ) be the case that transitivity of pairwise orderings may not hold. For HITs. We can batch b ratings in a HIT to reduce the number of example, worker 1 may decide that A > B and B > C, and worker HITs by a factor of b. The variance of the rating can be reduced 2 may decide that C > A. One way to resolve such ambiguities is by asking more workers to rate the item. The drawback is that each 

9 .item is rated independently of other items, and the relative ordering 4.2.2 Square Sort Microbenchmarks of an item pair’s mean ratings may not by fully consistent with the In this section, we compare the accuracy, latency, and price for ordering that would result if workers directly compared the pair. the query described in Section 2.3, in which workers sort squares by their size. 4.1.3 Hybrid Algorithm Comparison batching. In our first experiment, we sort a dataset We now propose a hybrid approach that initially orders the data with 40 squares by size. We first measure the accuracy of Compare using the rating-based sort and generates a list L. Each item li ∈ L as the group size S varies between 5, 10, and 20. Batches are gener- has an average rating µi , as well as a standard deviation σi computed ated so that every pair of items has at least 5 assignments. Our batch- from votes used to derive the rating. The idea of our hybrid approach generation algorithm may generate overlapping groups, so some pairs is to iteratively improve L by identifying subsets of S items that may may be shown more than 5 times. The accuracy is perfect when not be accurately ordered and using the comparison-based operator S = 5 and S = 10 (τ = 1.0 with respect to a perfect ordering). to order them. The user can control the resulting accuracy and cost The rate of workers accepting the tasks dramatically decreases when by specifying the number of iterations (where each iteration requires the group size is above 10 (e.g., the task takes 0.3 hours with group one additional HIT) to perform. size 5, but more than 1 hour with group size 10.) We stopped the We explored several techniques for selecting size-S windows for group size 20 experiment after several hours of uncompleted HITs. comparisons. We outline three representative approaches: We discuss this effect in more detail, and ways to deal with it, in Section 6. Random: In each iteration, pick S items randomly from L. Rating batching. We then measure the accuracy of the Rate im- Confidence-based: Let wi = {li , ..., li+S }, meaning wi contains plementation. The interface shows 10 sample squares, sampled ran- the S consecutive items lj ∈ L starting from item li . For each pair domly from the 40, and varies the batch size from 1 to 10, requiring of items a, b ∈ wi , we have their rating summary statistics (µa , σa ) 40 to 4 HITs, respectively. In all cases, the accuracy is lower than and (µb , σb ). Where µa < µb , we compute ∆a,b , the difference Compare, with an average τ of 0.78 (strong but not perfect rank- between one standard deviation above µa and one standard deviation ing correlation) and standard deviation of 0.058. While increasing below µb : batch size to large amounts made HITs less desirable for turkers and eventually increased latency, it did not have a noticeable effect on ac- ∆a,b = max(µa + σa − µb − σb , 0) curacy. We also found that 5 assignments per HIT resulted in similar For all windows wi , we then compute Ri = P accuracy to 10 assignments per HIT, suggesting diminishing returns (a,b)∈wi ∆a,b and order windows in decreasing order of Ri , such that windows with for this task. the most standard deviation overlap, and thus least confidence in their Rating granularity. Our next experiment is designed to measure if ratings, are reordered first. the granularity of the seven-point Likert scale affects the accuracy of the ordering as the number of distinct items increases. We fix the Sliding window: The algorithm picks window batch size at 5, and vary the size of the dataset from 20 to 50 in incre- ments of 5. The number of HITs vary from 4 to 10, respectively. As wi = {li mod |L| , ..., l(i+S) mod |L| } with varying batch size, the dataset size does not significantly impact with i starting at 1. In successive iterations, i is incremented by t accuracy (avg τ 0.798, std 0.042), suggesting that rating granularity (e.g., i = (i + t)), which the mod operation keeps the range in is stable with increasing dataset size. While combining 10 assign- [1, |L|]. If t is not a divisor of L, when successive windows wrap ments from two trials did reduce τ variance, it did not significantly around L, they will be offset from the previous passes. affect the average. 4.2 Experiments 4.2.3 Query Ambiguity: Sort vs. Rank We now describe experiments that compare the performance and The square sort microbenchmarks indicate that Compare is more accuracy effects of the Compare and Rate sort implementations, accurate than Rate. In our next experiment, we compare how in- as well as the improvements of our Hybrid optimizations. creasing the ambiguity of sorting tasks affects the accuracy of Rate The experiments compare the relative similarity of sorted lists us- relative to Compare. The goal is to test the utility of metrics that ing Kendall’s Tau (τ ), which is a measure used to compute rank- help predict 1) if the sort task is feasible at all, and 2) how closely correlation [7]. We use the τ − b variant, which allows two items Rate corresponds to Compare. The metric we use to answer 1) is to have the same rank order. The value varies between -1 (inverse a modified version of Fleiss’ κ (which we used for inter-reliability correlation), 0 (no correlation), and 1 (perfect correlation). rating in joins)4 , and the metric to answer 2) is τ . The experiment For each pair in Compare, we obtain at least 5 comparisons and uses both the squares and animals datasets. take the majority vote of those comparisons. For each item in Rate, We generated five queries that represent five sort tasks: we obtain 5 scores, and take the mean of those scores. We ran two Q1: Sort squares by size trials of each experiment. Q2: Sort animals by “Adult size” Q3: Sort animals by “Dangerousness” 4.2.1 Datasets Q4: Sort animals by “How much this animal belongs on Saturn” The squares dataset contains a synthetically generated set of squares. Q5: (Artificially) generate random Compare and Rate responses. Each square is n × n pixels, and the smallest is 20×20. A dataset of The instructions for Q3 and 4 were deliberately left open-ended to size N contains squares of sizes {(20+3∗i)×(20+3∗i)|i ∈ [0, N )}. increase the ambiguity. Q4 was intended to be a nonsensical query This dataset is designed so that the sort metric (square area) is clearly that we hoped would generate random answers. As we describe be- defined, and we know the correct ordering. low, the worker agreement for Q4’s Compare tasks was higher than The animals dataset contains 25 images of randomly chosen animals 4 Traditional Fleiss’ κ calculates priors for each label to compensate ranging from ants to humpback whales. In addition, we added an for bias in the dataset (e.g., if there are far more small animals than image of a rock and a dandelion to introduce uncertainty. This is big animals). We found this doesn’t work well for sort-based com- a dataset on which comparisons are less certain, and is designed to parator data due to correlation between comparator values, and so we show relative accuracies of comparison and rating-based operators. removed the compensating factor (the denominator in Fleiss’ κ). 

10 . )% (% "#(% !"'$% "#'% !"##"$%"&' !"'% !"#$ "#&% !"&$% "#$% !"&% "% *)% *$% *+% *&% *,% !"#$% !"#$% !% )!% *!% +!% &!% -./% -./!0.1234% 5.22.% 5.22.!0.1234% %$&'!($ ,-./01% 20.3/4.54% 67./089$:% 67./089+:% 201;-<4% ,-=4% 6: τ and κ metrics on 5 queries. Q5, which suggests that even for nonsensical questions, workers will 7: Hybrid sort algorithms on the 40-square dataset. apply and agree on some preconceived sort order. For lack of objective measures, we use the Compare results as ground truth. The results of running Compare on queries 2, 3, and 4 are as follows: Our final set of experiments measure how the hybrid approaches Size: ant, bee, flower, grasshopper, parrot, rock, rat, octopus, skunk, perform in terms of accuracy with increasing number of HITs. We tazmanian devil, turkey, eagle, lemur, hyena, dog, komodo dragon, aim to understand how the sort order of hybrid changes between baboon, wolf, panther, dolphin, elephant seal, moose, tiger, camel, Rank quality and Compare quality with each additional HIT. great white shark, hippo, whale The first experiment uses the 40-square dataset. The comparison Dangerousness: flower, ant, grasshopper, rock, bee, turkey, dolphin, interface shows 5 items at a time. We set window size S = 5 to be parrot, baboon, rat, tazmanian devil, lemur, camel, octopus, dog, ea- consistent with the number of items in a single comparison HIT. Fig- gle, elephant seal, skunk, hippo, hyena, great white shark, moose, ure 7 shows how τ improves with each additional HIT. Compare komodo dragon, wolf, tiger, whale, panther (upper right circle) orders the list perfectly, but costs 78 HITs to Belongs on Saturn5 : whale, octopus, dolphin, elephantseal, greatwhite- complete. In contrast, Rate (lower left square) achieves τ = 0.78, shark, bee, flower, grasshopper, hippo, dog, lempur, wolf, moose, but only costs 8 HITs (batch size=5). In addition to these two ex- camel, hyena, skunk, tazmaniandevil, tiger, baboon, eagle, parrot, tremes, we compared four schemes, based on those described in Sec- turkey, rat, panther, komododragon, ant, rock tion 4.1.3: random, confidence-based, windowing with t = 5 (Win- dow 5), and windowing with t = 6 (Window 6). Figure 6 show τ and κ for each of the five queries. Here κ is Overall, Window 6 performs best, achieving τ > .95 in under computed on the comparisons produced by the Compare tasks. The 30 additional HITs, and converging to τ = 1 in half the HITs that figure also shows the effect of computing these metrics on a random Compare requires. Window 5 performs poorly because t is a multi- sample of 10 of the squares/animals rather than the entire data set ple of the number of squares, so multiple passes over the data set (be- (the sample bars are from 50 different samples; error bars show the yond the 8th HIT) do not improve the ordering. As the list becomes standard deviation of each metric on these 50 samples.) more ordered, random is more likely to compare items that are cor- The results show that the ambiguous queries have progressively rectly ordered, and thus wastes comparisons. Confidence does not less worker agreement (κ) and progressively less agreement between perform as well as Window 6—prioritizing high-variance regions as- sorting and rating (τ ). While κ decreases between Q3 and Q4 (dan- sists with fixing local sort order mistakes, but does not systematically gerousness and Saturn), it is not as low in Q4 as it is in Q5 (Saturn move items that are far from their correct positions. In the sliding and random). This suggests that while there is little agreement be- window scheme, after several passes through the dataset items that tween workers on animals which belong on Saturn, their level of were far away from their correct position can migrate closer to the agreement is better than random. For example, Komodo Dragon correct location. was consistently rated as highly adaptable to Saturn’s environment. Finally, we executed Q2 (animal size query) using the hybrid scheme The decrease in κ with increasing ambiguity suggests that κ is a use- and found similar results between the approaches. Ultimately, the ful signal in identifying unsortable datasets. window-based approach performed the best and improved τ from τ is significantly lower for Q4 than for Q3, which suggests that .76 to .90 within 20 iterations. ordering by rating does not work well for Q4 and that we should probably use the Compare method for this workload rather than the Rate method. For Q1, Q2, and Q3, however, Rate agrees rea- sonably well with Compare, and because it is significantly cheaper, may be a better choice. Finally, we note that sampling 10 elements is an effective way to 4.3 Summary estimate both of these metrics, which means that we can run both In summary, we presented two sort interfaces and algorithms based Rate and Compare on samples, compute τ and κ, and decide on ratings (linear complexity) and comparisons (quadratic complex- whether to order the rest of the data set with Rate or Compare ity). We found that batching is an effective way to reduce the com- (depending on τ ), or to stop ordering at that point (if κ is very low.) plexity of sort tasks in both interfaces. We found that while signifi- cantly cheaper, ratings achieve sort orders close to but not as good as 4.2.4 Hybrid Approach comparisons. Using two metrics, τ and a modified κ, we were able to determine when a sort was too ambiguous (κ) and when rating 5 Note that while size and dangerousness have relatively stable or- performs commensurate with comparison (τ ). ders, the Saturn list varies drastically as indicated by low κ. For Using a hybrid window-based approach that started with ratings example, in three runs of the query, rock appeared at the end, near and refined with comparisons, we were able to get similar (τ > .95) the beginning, and in the middle of the list. accuracy to sorts at less than one-third the cost. 

11 . Operator Optimization # HITs to perform Smart Join with a 5x5 grid was relatively small. This il- Join Filter 43 lustrates the need for online selectivity estimation to determine when Join Filter + Simple 628 a crowd-based predicate will be useful. Join Filter + Naive 160 Query Accuracy: The numInScene task was very accurate, re- Join Filter + Smart 3x3 108 Join Filter + Smart 5x5 66 sulting in no errors compared to a manually-evaluated filter. The Join No Filter + Simple 1055 inScene join did less well, as some actors look similar, and some Join No Filter + Naive 211 scenes showed actors from the side; we had a small number of false Join No Filter + Smart 5x5 43 positives, but these were consistent across implementations. Finally, Order By Compare 61 the scene quality operator had high variance and was quite sub- Order By Rate 11 jective; in such cases Rate works just as well as Compare. Total (unoptimized) 1055 + 61 = 1116 Total (optimized) 66 + 11 = 77 5: Number of HITs for each operator optimization 6. DISCUSSION AND FUTURE WORK In this section, we discuss issues and lessons learned from our 5. END TO END QUERY implementation and efforts running jobs on Mechanical Turk. In the previous sections, we examined how different operator op- timizations affected price, accuracy, and latency, and evaluated them Reputation: While not directly related to database implementation, in isolation. In this section, we execute a complex query that utilizes it is important to remember that your identity carries reputation on both join and sort operators, and show that Qurk’s optimizations can MTurk. Turkers keep track of good and bad requesters, and share this reduce the overall number of HITs by a factor of 14.5 as compared information on message boards such as Turker Nation6 . By quickly to a naive approach, and still generate comparable results. approving completed work and responding to Turker requests when they contact you with questions, you can generate a good working relationship with Turkers. 5.1 Experimental Setup When we started as requesters, Turkers asked on Turker Nation if The query joins a table of movie frames and a table of actor photos, others knew whether we were trustworthy. A Turker responded: looking for frames containing only the actor. For each actor, the [requester name] is okay .... I don’t think you need to worry. He is query finds frames where the actor is the main focus of the frame great on communication, responds to messages and makes changes and orders the frames by how flattering they are: to the Hits as per our feedback. SELECT name, scene.img Turker feedback is also a signal for price appropriateness. For ex- FROM actors JOIN scenes ample, if a requester overpays for work, Turkers will send messages ON inScene(actors.img, scenes.img) asking for exclusive access to their tasks. AND POSSIBLY numInScene(scenes.img) > 1 ORDER BY name, quality(scenes.img) Choosing Batch Size: We showed that batching can dramatically re- duce the cost of sorts and joins. In studying different batch sizes, we The query uses three crowd-based UDFs: found batch sizes at which workers refused to perform tasks, leaving numInScene, a generative UDF that asks workers to select the num- our assignments uncompleted for hours at a time. As future work, it ber of people in the scene given the options (0, 1, 2, 3+, UNKNOWN). would be interesting to compare adaptive algorithms for estimating This UDF was designed to reduce the number of images input into the ideal batch size. Briefly, such an algorithm performs a binary the join operator. search on the batch size, reducing the size when workers refuse to do inScene, an EquiJoin UDF that shows workers images of actors and work or accuracy drops, and increasing the size when no noticeable scenes and asks the worker to identify pairs of images where the actor change to latency and accuracy is observed. is the main focus of the scene. As a word of caution, the process of adaptively finding the appro- quality, a Rank UDF that asks the worker to sort scene images by priate batch sizes can lead to worker frustration. The same Turker how flattering the scenes are. This task is highly subjective. that initially praised us in Section 6 became frustrated enough to list We tried several variants of each operator. For the numInScene us on Turker Nation’s “Hall of Shame:” filter we executed feature extraction with batch size 4. We also tried disabling the operator and allowing all scenes to be input to the join These are the “Compare celebrity pictures” Hits where you had to com- operator. For the inScene join, we use Simple, Naive batch 5, pare two pictures and say whether they were of the same person. The and Smart batch 3×3 and 5×5. For the quality sort, we used Hit paid a cent each. Now there are 5 pairs of pictures to be checked Compare with group size 5, and Rate batch 5. for the same pay. Another Requester reducing the pay drastically. The dataset was created by extracting 211 stills at one second in- Hence, batching has to be applied carefully. Over time, ideal start- tervals from a three-minute movie; actor profile photos came from ing batch sizes can be learned for various media types, such as joins the Web. on images vs. joins on videos. Worker Selection: We found that the QA method of Ipeirotis et 5.2 Results al. [6] works better than simple majority vote for combining multiple The results are summarized in Table 5. The bottom two lines show assignment answers and is able to effectively eliminate and identify that a simple approach based on a naive, unfiltered join plus compar- workers who generate spam answers. Majority vote can be badly isons requires 1116 hits, whereas applying our optimizations reduces skewed by low-quality answers and spam. this to 77 hits. We make a few observations: To allow us to compare across experiments, we elected not to ban Smart Join: Surprisingly, we found that workers were willing to workers from completing future tasks even if they were clearly gen- complete a 5x5 SmartJoin, despite its relative complexity. This may erating poor output. In a non-experimental scenario, one could use suggest that SmartJoin is preferred to naive batching. the output of the QA algorithm to ban Turkers found to produce poor Feature Extraction: We found that the benefit of numInScene results, reducing future costs. feature extraction was outweighed by its cost, as the the selectivity 6 of the predicate was only 55%, and the total number of HITs required http://turkers.proboards.com/ 

12 . One limitation of QA is that it is designed for categorical data, result accuracy is not improved by increasing worker wages. This when workers assign categories to records. Devising a similar method leads to our experiment design choice of studying how to reduce the for ordinal and interval data is interesting future work. number of HITs while maintaining accuracy and per-HIT cost. Scaling Up Datasets: In our experiments, we described techniques that provide order-of-magnitude cost reductions in executing joins 8. CONCLUSION and sorts. Still, scaling datasets by another order of magnitude or We presented an approach for executing joins and sorts in a declar- two would result in prohibitive costs due to the quadratic complex- ative database where humans are employed to process records. Our ity of both join and sort tasks. Hence, one important area of future system, Qurk, runs on top of crowdsourcing platforms like MTurk. work is to integrate human computation and machine learning, train- For join comparisons, we developed three different UIs (simple, naive ing classifiers to perform some of the work, and leaving humans to batching, and smart batching), and showed that the batching inter- peform the more difficult tasks. faces can reduce the total number of HITs to compute a join by an order of magnitude. We showed that feature filtering can pre-filter Whole Plan Budget Allocation: We have described how Qurk can join results to avoid cross products, and that our system can auto- determine and optimize the costs of individual query operators. An- matically select the best features. We presented three approaches to other important problem is how to assign a fixed amount of money sorting: comparison-based, rating-based, and a hybrid of the two. to an entire query plan. Additionally, when there is too much data We showed that rating often does comparably to pairwise compar- to process given a budget, we would like Qurk to be able to decide isons, using far fewer HITs, and presented signals κ and τ that can which data items to process in more detail. be used to determine if a data set is sortable, and how well rating per- forms relative to comparison. We also present a hybrid scheme that Iterative Debugging: In implementing queries in Qurk, we found uses a combination of rating and comparing to produce a more accu- that workflows frequently failed because of poor Turker interface de- rate result than rating while using fewer HITs than comparison. We sign or the wording of a question. Crowd-powered workflow engines showed on several real-world datasets that we can greatly reduce the could benefit from tools for iterative debugging. total cost of queries without sacrificing accuracy – we reduced the As future work, we want to design a SQL EXPLAIN-like interface cost of a join on a celebrity image data set from $67 to about $3, a which annotates operators with signals such as rater agreement, com- sort by 2× the worst-case cost, and reduced the cost of an end-to-end parison vs. rating agreement, and other indicators of where a query example by a factor of 14.5. has gone astray. Additionally, it is important to generate represen- tative datasets for trial runs on new workflows before expending the entire budget on a buggy user interface element. 9. REFERENCES [1] M. S. Bernstein et al. Soylent: a word processor with a crowd inside. In UIST, pages 313–322, New York, NY, USA, 2010. 7. RELATED WORK [2] J. P. Bigham et al. Vizwiz: nearly real-time answers to visual questions. In UIST, pages 333–342, 2010. The database community has recently seen increasing interest in [3] A. P. Dawid and A. M. Skene. Maximum likelihood estimation of crowdsourced databases. Franklin et al. present CrowdDB [5], a observer error-rates using the em algorithm. Journal of the Royal database with a declarative interface and operators for handling joins, Statistical Society., 28(1):pp. 20–28, 1979. sorts, and generative queries in their data definition language. Their [4] J. L. Fleiss. Measuring nominal scale agreement among many raters. In experiments explore the properties of MTurk and show the feasibility Psychological Bulletin, 1971. of joins and sorts, but they do not provide a detailed discussion of im- [5] M. Franklin, D. Kossmann, T. Kraska, S. Ramesh, and R. Xin. plementation alternatives or performance tradeoffs. Our contribution CrowdDB: Answering queries with crowdsourcing. In SIGMOD 2011. is to study how to achieve order-of-magnitude price improvements [6] P. G. Ipeirotis, F. Provost, and J. Wang. Quality management on while maintaining result accuracy. Parameswaran et al. present the amazon mechanical turk. In SIGKDD Workshop on Human Computation, pages 64–67, New York, NY, USA, 2010. ACM. vision for a crowdsourced database including a Datalog-based query [7] M. G. Kendall. A new measure of rank correlation. Biometrika, language for querying humans, and provide some thoughts on how 30(1-2):81–93, 1938. to reason about uncertain worker responses [13]. [8] A. Kittur, B. Smus, and R. E. Kraut. CrowdForge: Crowdsourcing Systems for posting tasks to MTurk are available outside the databases Complex Work. Technical report, 2011. community. TurKit [10] is a system and programming model by Lit- [9] R. Likert. A technique for the measurement of attitudes. Archives of tle et al. that allows developers to iteratively build MTurk-based ap- Psychology, 140:1–55, 1932. plications while caching HIT results between program runs. Kittur et [10] G. Little et al. Turkit: human computation algorithms on mechanical al. present CrowdForge [8], a MapReduce-style model for large task turk. In UIST, pages 57–66, 2010. decomposition and verification. [11] A. Marcus, E. Wu, et al. Crowdsourced databases: Query processing with people. In CIDR 2011. Because we retrieve multiple worker responses to each question, [12] W. Mason and D. J. Watts. Financial incentives and the “performance we must decide how to arrive at the correct answer given several. A of crowds”. HCOMP 2009. simple approach, used by CrowdFlower7 , is to require gold standard [13] A. Parameswaran and N. Polyzotis. Answering queries using data with which to test worker quality, and ban workers who perform databases, humans and algorithms. In CIDR 2011. poorly on the gold standard. For categorical data, selecting a ma- jority vote of responses is also powerful. Dawid and Skene present an expectation maximization technique for for iteratively estimating worker and result quality [3] in the absense of gold standard data. Ipeirotis et al. modify this technique to consider not only worker quality, but also correct for bias between workers [6] on categorical data. We utilize this last technique to improve join results. Mason and Watts study the effects of price on quantity and quality of work [12]. They find that workers are willing to perform more tasks when paid more. They also find that for a given task difficulty, 7 http://crowdflower.com