Stanford InfoLab Publication Server

Human-assisted Graph Search: It's Okay to Ask Questions

Parameswaran, Aditya and Das Sarma, Anish and Garcia-Molina, Hector and Polyzotis, Neoklis and Widom, Jennifer (2011) Human-assisted Graph Search: It's Okay to Ask Questions. Proceedings of the Very Large Database Conference (VLDB), 4 (5).




We consider the problem of human-assisted graph search: given a directed acyclic graph with some (unknown) target node(s), we consider the problem of finding the target node(s) by asking an omniscient human questions of the form ``Is there a target node that is reachable from the current node?''. This general problem has applications in many domains that can utilize human intelligence, including curation of hierarchies, debugging workflows, image segmentation and categorization, interactive search and filter synthesis. To our knowledge, this work provides the first formal algorithmic study of the optimization of human computation for this problem. We study various dimensions of the problem space, providing algorithms and complexity results. Our framework and algorithms can be used in the design of an optimizer for crowd-sourcing platforms such as Mechanical Turk.

Item Type:Article
Uncontrolled Keywords:human computation, optimization, crowd-sourcing, theory, algorithms, asking people
ID Code:970
Deposited By:Aditya Parameswaran
Deposited On:01 Jun 2010 02:27
Last Modified:01 Jul 2011 15:12

Download statistics

Repository Staff Only: item control page