Counting with the crowd

In this paper, we address the problem of selectivity estimation in a crowdsourced database. Specifically, we develop several tech-niques for using workers on a crowdsourcing platform like Ama-zon’s Mechanical Turk to estimate the fraction of items in a dataset (e.g., a collection of photos) that satisfy some property or predi-cate (e.g., photos of trees). We do this without explicitly iterat-ing through every item in the dataset. This is important in crowd-sourced query optimization to support predicate ordering and in query evaluation, when performing a GROUP BY operation with a COUNT or AVG aggregate. We compare sampling item labels, a traditional approach, to showing workers a collection of items and asking them to estimate how many satisfy some predicate. Addi-tionally, we develop techniques to eliminate spammers and collud-ing attackers trying to skew selectivity estimates when using this count estimation approach. We find that for images, counting can be much more effective than sampled labeling, reducing the amount of work necessary to arrive at an estimate that is within 1 % of the true fraction by up to an order of magnitude, with lower worker latency. We also find that sampled labeling outperforms count es-timation on a text processing task, presumably because people are better at quickly processing large batches of images than they are at reading strings of text. Our spammer detection technique, which is applicable to both the label- and count-based approaches, can improve accuracy by up to two orders of magnitude. 1