Paper Info
Title
Human-assisted graph search: it's okay to ask questions
Abstract
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 crowd-sourcing platforms such as Mechanical Turk.
Year
DOI
Venue
2011
10.14778/1952376.1952377
Clinical Orthopaedics and Related Research
Keywords
Field
DocType
human computation,acyclic graph,target node,human intelligence,general problem,problem space,human-assisted graph search,omniscient human question,formal algorithmic study,current node
Data mining,Computer science,Image segmentation,Fringe search,Theoretical computer science,Directed acyclic graph,Null graph,Bidirectional search,Database,Moral graph,Best-first search,Graph (abstract data type)
Journal
Volume
Issue
ISSN
4
5
Proceedings of the VLDB Endowment (PVLDB), Vol. 4, No. 5, pp. 267-278 (2011)
Citations 
PageRank 
References 
76
4.23
21
Authors
5
Name
Order
Citations
PageRank
Aditya Parameswaran1111278.56
Anish Das Sarma22028104.57
Héctor García-Molina3243595652.13
Neoklis Polyzotis42078138.76
Jennifer Widom5161502524.75