{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T13:09:02Z","timestamp":1723900142484},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>Recent research has shown that crowd sourcing can be used effectively to solve problems that are difficult for computers, e.g., optical character recognition and identification of the structural configuration of natural proteins. In this paper we propose to use the power of the crowd to address yet another difficult problem that frequently occurs in a daily life - answering planning queries whose output is a sequence of objects\/actions, when the goal, i.e, the notion of \"best output\", is hard to formalize. For example, planning the sequence of places\/attractions to visit in the course of a vacation, where the goal is to enjoy the resulting vacation the most, or planning the sequence of courses to take in an academic schedule planning, where the goal is to obtain solid knowledge of a given subject domain. Such goals may be easily understandable by humans, but hard or even impossible to formalize for a computer.<\/jats:p>\n          <jats:p>We present a novel algorithm for efficiently harnessing the crowd to assist in answering such planning queries. The algorithm builds the desired plans incrementally, choosing at each step the 'best' questions so that the overall number of questions that need to be asked is minimized. We prove the algorithm to be optimal within its class and demonstrate experimentally its effectiveness and efficiency.<\/jats:p>","DOI":"10.14778\/2536360.2536369","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"697-708","source":"Crossref","is-referenced-by-count":23,"title":["Answering planning queries with the crowd"],"prefix":"10.14778","volume":"6","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[{"name":"School of Computer Science, Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilia","family":"Lotosh","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Slava","family":"Novgorodov","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,7]]},"reference":[{"issue":"6","key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1109\/TKDE.2005.99","volume":"17","author":"Adomavicius G.","year":"2005","unstructured":"G. Adomavicius and A. Tuzhilin . Toward the next generation of recommender systems. IEEE Trans. Knowl. Data Eng. , 17 ( 6 ): 734 - 749 , 2005 . G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems. IEEE Trans. Knowl. Data Eng., 17(6):734-749, 2005.","journal-title":"Toward the next generation of recommender systems. IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_2_1","first-page":"1261","volume-title":"ICDE","author":"Boim R.","year":"2012","unstructured":"R. Boim , O. Greenshpan , T. Milo , S. Novgorodov , N. Polyzotis , and W.-C. Tan . Asking the right questions in crowd data sourcing . In ICDE , pages 1261 - 1264 , 2012 . R. Boim, O. Greenshpan, T. Milo, S. Novgorodov, N. Polyzotis, and W.-C. Tan. Asking the right questions in crowd data sourcing. In ICDE, pages 1261-1264, 2012."},{"key":"e_1_2_1_3_1","first-page":"1251","volume-title":"SIGMOD","author":"Chen G.","year":"2011","unstructured":"G. Chen , C. Liu , M. Lu , B. C. Ooi , S. Ying , A. Tung , D. Zhang , and M. Zhang . A cross-service travel engine for trip planning . In SIGMOD , pages 1251 - 1254 , 2011 . G. Chen, C. Liu, M. Lu, B. C. Ooi, S. Ying, A. Tung, D. Zhang, and M. Zhang. A cross-service travel engine for trip planning. In SIGMOD, pages 1251-1254, 2011."},{"key":"e_1_2_1_4_1","volume-title":"AAAI","author":"Dai P.","year":"2010","unstructured":"P. Dai , Mausam, and D. S. Weld . Decision-theoretic control of crowd-sourced workflows . In AAAI , 2010 . P. Dai, Mausam, and D. S. Weld. Decision-theoretic control of crowd-sourced workflows. In AAAI, 2010."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/2448496.2448524","volume-title":"ICDT","author":"Davidson S.","year":"2013","unstructured":"S. Davidson , S. Khanna , T. Milo , and S. Roy . Using the crowd for top-k and group-by queries . In ICDT , pages 225 - 236 , 2013 . S. Davidson, S. Khanna, T. Milo, and S. Roy. Using the crowd for top-k and group-by queries. In ICDT, pages 225-236, 2013."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1145\/2187836.2187942","volume-title":"WWW","author":"Deutch D.","year":"2012","unstructured":"D. Deutch , O. Greenshpan , B. Kostenko , and T. Milo . Declarative platform for data sourcing games . In WWW , pages 779 - 788 , 2012 . D. Deutch, O. Greenshpan, B. Kostenko, and T. Milo. Declarative platform for data sourcing games. In WWW, pages 779-788, 2012."},{"issue":"4","key":"e_1_2_1_7_1","first-page":"86","volume":"54","author":"Doan A.","year":"2011","unstructured":"A. Doan , R. Ramakrishnan , and A. Y. Halevy . Crowdsourcing systems on the world-wide web. Commun. ACM , 54 ( 4 ): 86 - 96 , 2011 . A. Doan, R. Ramakrishnan, and A. Y. Halevy. Crowdsourcing systems on the world-wide web. Commun. ACM, 54(4):86-96, 2011.","journal-title":"Crowdsourcing systems on the world-wide web. Commun. ACM"},{"issue":"4","key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1016\/S0022-0000(03)00026-6","volume":"66","author":"Fagin R.","year":"2003","unstructured":"R. Fagin , A. Lotem , and M. Naor . Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. , 66 ( 4 ): 614 - 656 , 2003 . R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci., 66(4):614-656, 2003.","journal-title":"Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci."},{"key":"e_1_2_1_9_1","volume-title":"SIGMOD","author":"Franklin M. J.","year":"2011","unstructured":"M. J. Franklin , D. Kossmann , T. Kraska , S. Ramesh , and R. Xin . Crowddb: answering queries with crowdsourcing . In SIGMOD , 2011 . M. J. Franklin, D. Kossmann, T. Kraska, S. Ramesh, and R. Xin. Crowddb: answering queries with crowdsourcing. In SIGMOD, 2011."},{"key":"e_1_2_1_10_1","volume-title":"Automated planning - theory and practice","author":"Ghallab M.","year":"2004","unstructured":"M. Ghallab , D. S. Nau , and P. Traverso . Automated planning - theory and practice . Elsevier , 2004 . M. Ghallab, D. S. Nau, and P. Traverso. Automated planning - theory and practice. Elsevier, 2004."},{"key":"e_1_2_1_11_1","volume-title":"Survey Methodology","author":"Groves R.","year":"2009","unstructured":"R. Groves , F. J. Fowler , M. Couper , J. Lepkowski , E. Singer , and R. Tourangeau . Survey Methodology . John Wiley and Sons , 2009 . R. Groves, F. J. Fowler, M. Couper, J. Lepkowski, E. Singer, and R. Tourangeau. Survey Methodology. John Wiley and Sons, 2009."},{"key":"e_1_2_1_12_1","first-page":"385","volume-title":"SIGMOD Conference","author":"Guo S.","year":"2012","unstructured":"S. Guo , A. G. Parameswaran , and H. Garcia-Molina . So who won?: dynamic max discovery with the crowd . In SIGMOD Conference , pages 385 - 396 , 2012 . S. Guo, A. G. Parameswaran, and H. Garcia-Molina. So who won?: dynamic max discovery with the crowd. In SIGMOD Conference, pages 385-396, 2012."},{"key":"e_1_2_1_13_1","author":"Hart P.","year":"1968","unstructured":"P. Hart , N. Nilsson , and B. Raphael . A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on , 1968 . P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on, 1968.","journal-title":"Systems Science and Cybernetics, IEEE Transactions on"},{"key":"e_1_2_1_14_1","unstructured":"H. Kaplan I. Lotosh T. Milo and S. Novgorodov. Answering planning queries with the crowd (technical report) http:\/\/slavanov.com\/research\/crowdplanr-tr.pdf.  H. Kaplan I. Lotosh T. Milo and S. Novgorodov. Answering planning queries with the crowd (technical report) http:\/\/slavanov.com\/research\/crowdplanr-tr.pdf."},{"key":"e_1_2_1_15_1","first-page":"491","volume-title":"UAI","author":"Lin C. H.","year":"2012","unstructured":"C. H. Lin , Mausam, and D. S. Weld . Crowdsourcing control: Moving beyond multiple choice . In UAI , pages 491 - 500 , 2012 . C. H. Lin, Mausam, and D. S. Weld. Crowdsourcing control: Moving beyond multiple choice. In UAI, pages 491-500, 2012."},{"issue":"10","key":"e_1_2_1_16_1","first-page":"1040","volume":"5","author":"Liu X.","year":"2012","unstructured":"X. Liu , M. Lu , B. C. Ooi , Y. Shen , S. Wu , and M. Zhang . Cdas: A crowdsourcing data analytics system. PVLDB , 5 ( 10 ): 1040 - 1051 , 2012 . X. Liu, M. Lu, B. C. Ooi, Y. Shen, S. Wu, and M. Zhang. Cdas: A crowdsourcing data analytics system. PVLDB, 5(10):1040-1051, 2012.","journal-title":"Cdas: A crowdsourcing data analytics system. PVLDB"},{"key":"e_1_2_1_17_1","volume-title":"ICDE","author":"Lotosh I.","year":"2013","unstructured":"I. Lotosh , T. Milo , and S. Novgorodov . Crowdplanr: Planning made easy with crowd . In ICDE , 2013 . I. Lotosh, T. Milo, and S. Novgorodov. Crowdplanr: Planning made easy with crowd. In ICDE, 2013."},{"key":"e_1_2_1_18_1","first-page":"275","volume-title":"CIKM","author":"Ma H.","year":"2009","unstructured":"H. Ma , R. Chandrasekar , C. Quirk , and A. Gupta . Improving search engines using human computation games . In CIKM , pages 275 - 284 , 2009 . H. Ma, R. Chandrasekar, C. Quirk, and A. Gupta. Improving search engines using human computation games. In CIKM, pages 275-284, 2009."},{"key":"e_1_2_1_19_1","first-page":"211","volume-title":"CIDR","author":"Marcus A.","year":"2011","unstructured":"A. Marcus , E. Wu , S. Madden , and R. C. Miller . Crowdsourced databases: Query processing with people . In CIDR , pages 211 - 214 , 2011 . A. Marcus, E. Wu, S. Madden, and R. C. Miller. Crowdsourced databases: Query processing with people. In CIDR, pages 211-214, 2011."},{"key":"e_1_2_1_20_1","unstructured":"Amazon's mechanical turk. https:\/\/www.mturk.com\/.  Amazon's mechanical turk. https:\/\/www.mturk.com\/."},{"key":"e_1_2_1_21_1","first-page":"361","volume-title":"SIGMOD","author":"Parameswaran A. G.","year":"2012","unstructured":"A. G. Parameswaran , H. Garcia-Molina , H. Park , N. Polyzotis , A. Ramesh , and J. Widom . Crowdscreen: algorithms for filtering data with humans . In SIGMOD , pages 361 - 372 , 2012 . A. G. Parameswaran, H. Garcia-Molina, H. Park, N. Polyzotis, A. Ramesh, and J. Widom. Crowdscreen: algorithms for filtering data with humans. In SIGMOD, pages 361-372, 2012."},{"key":"e_1_2_1_22_1","first-page":"160","volume-title":"CIDR","author":"Parameswaran A. G.","year":"2011","unstructured":"A. G. Parameswaran and N. Polyzotis . Answering queries using humans, algorithms and databases . In CIDR , pages 160 - 166 , 2011 . A. G. Parameswaran and N. Polyzotis. Answering queries using humans, algorithms and databases. In CIDR, pages 160-166, 2011."},{"issue":"12","key":"e_1_2_1_23_1","first-page":"1990","volume":"5","author":"Park H.","year":"2012","unstructured":"H. Park , R. Pang , A. G. Parameswaran , H. Garcia-Molina , N. Polyzotis , and J. Widom . Deco: A system for declarative crowdsourcing. PVLDB , 5 ( 12 ): 1990 - 1993 , 2012 . H. Park, R. Pang, A. G. Parameswaran, H. Garcia-Molina, N. Polyzotis, and J. Widom. Deco: A system for declarative crowdsourcing. PVLDB, 5(12):1990-1993, 2012.","journal-title":"Deco: A system for declarative crowdsourcing. PVLDB"},{"issue":"6","key":"e_1_2_1_24_1","first-page":"538","volume":"5","author":"Selke J.","year":"2012","unstructured":"J. Selke , C. Lofi , and W.-T. Balke . Pushing the boundaries of crowd-enabled databases with query-driven schema expansion. PVLDB , 5 ( 6 ): 538 - 549 , 2012 . J. Selke, C. Lofi, and W.-T. Balke. Pushing the boundaries of crowd-enabled databases with query-driven schema expansion. PVLDB, 5(6):538-549, 2012.","journal-title":"PVLDB"},{"key":"e_1_2_1_25_1","first-page":"989","author":"Venetis P.","year":"2012","unstructured":"P. Venetis , H. Garcia-Molina , K. Huang , and N. Polyzotis . Max algorithms in crowdsourcing environments. In WWW, pages 989 - 998 , 2012 . P. Venetis, H. Garcia-Molina, K. Huang, and N. Polyzotis. Max algorithms in crowdsourcing environments. In WWW, pages 989-998, 2012.","journal-title":"Max algorithms in crowdsourcing environments. In WWW, pages"},{"issue":"8","key":"e_1_2_1_26_1","first-page":"58","volume":"51","author":"von Ahn L.","year":"2008","unstructured":"L. von Ahn and L. Dabbish . Designing games with a purpose. Commun. ACM , 51 ( 8 ): 58 - 67 , 2008 . L. von Ahn and L. Dabbish. Designing games with a purpose. Commun. ACM, 51(8):58-67, 2008.","journal-title":"Designing games with a purpose. Commun. ACM"},{"issue":"11","key":"e_1_2_1_27_1","first-page":"1483","volume":"5","author":"Wang J.","year":"2012","unstructured":"J. Wang , T. Kraska , M. J. Franklin , and J. Feng . Crowder: Crowdsourcing entity resolution. PVLDB , 5 ( 11 ): 1483 - 1494 , 2012 . J. Wang, T. Kraska, M. J. Franklin, and J. Feng. Crowder: Crowdsourcing entity resolution. PVLDB, 5(11):1483-1494, 2012.","journal-title":"Crowder: Crowdsourcing entity resolution. PVLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536360.2536369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:52:11Z","timestamp":1672221131000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536360.2536369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":27,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.14778\/2536360.2536369"],"URL":"https:\/\/doi.org\/10.14778\/2536360.2536369","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}