The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2016.12
URN: urn:nbn:de:0030-drops-57817
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5781/
Go to the corresponding LIPIcs Volume Portal

Groz, Benoit ; Levin, Ezra ; Meilijson, Isaac ; Milo, Tova

Filtering With the Crowd: CrowdScreen Revisited

pdf-format:
11.pdf (0.7 MB)

Abstract

Filtering a set of items, based on a set of properties that can be verified by humans, is a common application of CrowdSourcing. When the workers are error-prone, each item is presented to multiple users, to limit the probability of misclassification. Since the Crowd is a relatively expensive resource, minimizing the number of questions per item may naturally result in big savings. Several algorithms to address this minimization problem have been presented in the CrowdScreen framework by Parameswaran et al. However, those algorithms do not scale well and therefore cannot be used in scenarios where high accuracy is required in spite of high user error rates. The goal of this paper is thus to devise algorithms that can cope with such situations. To achieve this, we provide new theoretical insights to the problem, then use them to develop a new efficient algorithm. We also propose novel optimizations for the algorithms of CrowdScreen that improve their scalability. We complement our theoretical study by an experimental evaluation of the algorithms on a large set of synthetic parameters as well as real-life crowdsourcing scenarios, demonstrating the advantages of our solution.

BibTeX - Entry

@InProceedings{groz_et_al:LIPIcs:2016:5781,
  author =	{Benoit Groz and Ezra Levin and Isaac Meilijson and Tova Milo},
  title =	{{Filtering With the Crowd: CrowdScreen Revisited}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Wim Martens and Thomas Zeume},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5781},
  URN =		{urn:nbn:de:0030-drops-57817},
  doi =		{10.4230/LIPIcs.ICDT.2016.12},
  annote =	{Keywords: CrowdSourcing, filtering, algorithms, sprt, hypothesis testing}
}

Keywords: CrowdSourcing, filtering, algorithms, sprt, hypothesis testing
Collection: 19th International Conference on Database Theory (ICDT 2016)
Issue Date: 2016
Date of publication: 14.03.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI