TY - JOUR
T1 - Human-assisted graph search
T2 - It's okay to ask questions
AU - Parameswaran, Aditya
AU - Das Sarma, Anish
AU - Garcia-Molina, Hector
AU - Polyzotis, Neoklis
AU - Widom, Jennifer
PY - 2011/2
Y1 - 2011/2
N2 - 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. We also compare the performance of our algorithm against other algorithms, for the problem of webpage categorization on a real taxonomy. Our framework and algorithms can be used in the design of an optimizer for crowdsourcing platforms such as Mechanical Turk.
AB - 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. We also compare the performance of our algorithm against other algorithms, for the problem of webpage categorization on a real taxonomy. Our framework and algorithms can be used in the design of an optimizer for crowdsourcing platforms such as Mechanical Turk.
UR - http://www.scopus.com/inward/record.url?scp=79960245747&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960245747&partnerID=8YFLogxK
U2 - 10.14778/1952376.1952377
DO - 10.14778/1952376.1952377
M3 - Article
AN - SCOPUS:79960245747
SN - 2150-8097
VL - 4
SP - 267
EP - 278
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 5
ER -