{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T07:36:47Z","timestamp":1769931407182,"version":"3.49.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>\n            We consider the problem of\n            <jats:italic>human-assisted graph search<\/jats:italic>\n            : 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.\n          <\/jats:p>","DOI":"10.14778\/1952376.1952377","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"267-278","source":"Crossref","is-referenced-by-count":96,"title":["Human-assisted graph search"],"prefix":"10.14778","volume":"4","author":[{"given":"Aditya","family":"Parameswaran","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anish Das","family":"Sarma","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hector","family":"Garcia-Molina","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neoklis","family":"Polyzotis","sequence":"additional","affiliation":[{"name":"UC Santa Cruz"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer","family":"Widom","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804683"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1357054.1357127"},{"key":"e_1_2_1_3_1","volume-title":"CIDR '11","author":"A.","unstructured":"A. Parameswaran et. al. Answering queries using humans, algorithms and databases . In CIDR '11 . A. Parameswaran et. al. Answering queries using humans, algorithms and databases. In CIDR '11."},{"key":"e_1_2_1_4_1","unstructured":"A. Parameswaran et. al. Human-assisted graph search: It's okay to ask questions. Stanford Infolab http:\/\/ilpubs.stanford.edu:8090\/970\/.   A. Parameswaran et. al. Human-assisted graph search: It's okay to ask questions. Stanford Infolab http:\/\/ilpubs.stanford.edu:8090\/970\/."},{"key":"e_1_2_1_5_1","volume-title":"Computer Vision and Pattern Recognition Workshops","author":"A.","year":"2008","unstructured":"A. Sorokin et. al. Utility data annotation with amazon mechanical turk . Computer Vision and Pattern Recognition Workshops , 2008 . A. Sorokin et. al. Utility data annotation with amazon mechanical turk. Computer Vision and Pattern Recognition Workshops, 2008."},{"key":"e_1_2_1_7_1","unstructured":"C. Bishop. Pattern Recognition and Machine Learning. 2006 edition.   C. Bishop. Pattern Recognition and Machine Learning . 2006 edition."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-4571(2000)9999:9999%3C::AID-ASI1002%3E3.0.CO;2-B"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142055.1142067"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1631272.1631339"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378704.1378719"},{"key":"e_1_2_1_12_1","volume-title":"Computers and Intractability","author":"M.","year":"1990","unstructured":"M. Garey et. al. Computers and Intractability ; A Guide to the Theory of NP-Completeness. W. H. Freeman & amp; Co., 1990 . M. Garey et. al. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co., 1990."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559797"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480508"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/312624.312670"},{"key":"e_1_2_1_16_1","first-page":"254","volume-title":"EMNLP '08","author":"R.","year":"2008","unstructured":"R. Snow et. al. Cheap and fast---but is it good?: evaluating non-expert annotations for natural language tasks . In EMNLP '08 , pages 254 -- 263 , 2008 . R. Snow et. al. Cheap and fast---but is it good?: evaluating non-expert annotations for natural language tasks. In EMNLP '08, pages 254--263, 2008."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11799511_24"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376701"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206012"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775087"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376716"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007582"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1952376.1952377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:55:33Z","timestamp":1672224933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1952376.1952377"}},"subtitle":["it's okay to ask questions"],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.14778\/1952376.1952377"],"URL":"https:\/\/doi.org\/10.14778\/1952376.1952377","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,2]]}}}