{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:04Z","timestamp":1750221004501,"version":"3.41.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,8]],"date-time":"2020-02-08T00:00:00Z","timestamp":1581120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>\n            As most users do\n            <jats:italic>not<\/jats:italic>\n            precisely know the structure and\/or the content of databases, their queries do\n            <jats:italic>not<\/jats:italic>\n            exactly reflect their information needs. The database management system (DBMS) may interact with users and use their feedback on the returned results to learn the information needs behind their queries. Current query interfaces assume that users do\n            <jats:italic>not<\/jats:italic>\n            learn and modify the way they express their information needs in the form of queries during their interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS and their learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do\n            <jats:italic>not<\/jats:italic>\n            modify their strategies, they cannot discover the information needs behind users\u2019 queries effectively. We model the interaction between the user and the DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in the form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users\u2019 strategies and proves that it improves the effectiveness of answering queries, stochastically speaking. We propose two efficient implementations of this method over large relational databases. Our extensive empirical studies over real-world query workloads indicate that our algorithms are efficient and effective.\n          <\/jats:p>","DOI":"10.1145\/3351450","type":"journal-article","created":{"date-parts":[[2020,2,8]],"date-time":"2020-02-08T09:03:56Z","timestamp":1581152636000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Game-theoretic Approach to Data Interaction"],"prefix":"10.1145","volume":"45","author":[{"given":"Ben","family":"McCamish","sequence":"first","affiliation":[{"name":"Oregon State University, Corvallis, OR USA"}]},{"given":"Vahid","family":"Ghadakchi","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, OR, USA"}]},{"given":"Arash","family":"Termehchy","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, OR, USA"}]},{"given":"Behrouz","family":"Touri","sequence":"additional","affiliation":[{"name":"University of California San Diego, La Jolla, CA, USA"}]},{"given":"Eduardo","family":"Cotilla-Sanchez","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, OR, USA"}]},{"given":"Liang","family":"Huang","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, OR, USA"}]},{"given":"Soravit","family":"Changpinyo","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,2,8]]},"reference":[{"volume-title":"Foundations of Databases: The Logical Level","author":"Abiteboul Serge","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465220"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060779"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/09528130902823656"},{"key":"e_1_2_1_7_1","article-title":"Learning join queries from user examples","volume":"40","author":"Bonifati Angela","year":"2015","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728914"},{"key":"e_1_2_1_9_1","article-title":"Reinforcement learning in information searching","volume":"18","author":"Cen Yonghua","year":"2013","journal-title":"Inf. Res.: Int. Elect. J."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02279-1_2"},{"key":"e_1_2_1_11_1","article-title":"Probabilistic information retrieval approach for ranking of database query results","volume":"31","author":"Chaudhuri Surajit","year":"2006","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"volume-title":"Mahmassani","year":"2009","author":"Chen R.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559966"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"I. Cho and D. Kreps. 1987. Signaling games and stable equilibria. Quart. J. Econ. 102 (1987).  I. Cho and D. Kreps. 1987. Signaling games and stable equilibria. Quart. J. Econ. 102 (1987).","DOI":"10.2307\/1885060"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.2009.01509.x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/1882186"},{"volume-title":"Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems (AAMAS\u201914)","year":"2014","author":"Das Sanmay","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16170-4_11"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610523"},{"volume-title":"Bergstroma","year":"2007","author":"Donaldson Matina C.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1869916"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15251-1_19"},{"volume-title":"Roth","year":"1995","author":"Erev Ido","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201904)","year":"2004","author":"Ghosh Arjita","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008992.1009079"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2914798"},{"volume-title":"The New Palgrave Dictionary of Economics: Design of Experiments and Behavioral Economics","author":"Teck Ho.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-012-9197-9"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50080-X"},{"volume-title":"Reinforcement learning in signaling game. arXiv preprint arXiv:1103.5818","year":"2011","author":"Hu Yilei","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2207676.2208591"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2731084"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247483"},{"volume-title":"Proceedings of the International Conference on Management of Data (SIGMOD\u201916)","year":"2016","author":"Kandula Srikanth","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880175"},{"volume-title":"Chris Meek et al","year":"2007","author":"Koller Daphne","key":"e_1_2_1_39_1"},{"volume-title":"Introduction to Probability Theory and Statistical Inference","author":"Larson Harold J.","key":"e_1_2_1_40_1"},{"volume-title":"Convention","year":"1969","author":"Lewis David","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831369"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816756"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609629"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247495"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.092080099"},{"volume-title":"An Introduction to Information Retrieval","author":"Manning Christopher","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196899"},{"volume-title":"A signaling game approach to databases querying and interaction. arXiv preprint arXiv:1603.04068","year":"2016","author":"McCamish Ben","key":"e_1_2_1_49_1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382438.2382439"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553557"},{"volume-title":"Krakauer","year":"1999","author":"Nowak Martin A.","key":"e_1_2_1_52_1"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390255"},{"volume-title":"Herbert Robbins Selected Papers","author":"Robbins Herbert","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(05)80020-X"},{"key":"e_1_2_1_57_1","first-page":"1","article-title":"Some topics in two-person games","volume":"52","author":"Shapley Lloyd S.","year":"1964","journal-title":"Adv. Game Theor."},{"volume-title":"Multi-agent reinforcement learning: A critical survey. Web Manuscript","year":"2003","author":"Shoham Yoav","key":"e_1_2_1_58_1"},{"volume-title":"Reinforcement learning and human behavior. Curr. Opin. Neurobiol. 25 (04\/2014","year":"2014","author":"Shteingart Hanan","key":"e_1_2_1_59_1"},{"key":"e_1_2_1_60_1","first-page":"399","article-title":"Ranked bandits in metric spaces: Learning diverse rankings over large document collections","author":"Slivkins Aleksandrs","year":"2013","journal-title":"J. Mach. Learn. Res. 14"},{"volume-title":"Barto","year":"1998","author":"Sutton Richard S.","key":"e_1_2_1_61_1"},{"volume-title":"Game Theory: An Introduction","year":"2013","author":"Tadelis Steve","key":"e_1_2_1_62_1"},{"volume-title":"Proceedings of the International Conference on Management of Data (SIGMOD\u201909)","author":"Tran Q.","key":"e_1_2_1_63_1"},{"volume-title":"Nash equilibria for an evolutionary language game. J. Math. Biol. 41","year":"2000","author":"Trapa Peter","key":"e_1_2_1_64_1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741104"},{"key":"e_1_2_1_66_1","unstructured":"Robert L. Wolpert. 2010. Introduction to martingales. (2010). https:\/\/www2.stat.duke.edu\/courses\/Fall10\/sta205\/lec\/topics\/mg.pdf.  Robert L. Wolpert. 2010. Introduction to martingales. (2010). https:\/\/www2.stat.duke.edu\/courses\/Fall10\/sta205\/lec\/topics\/mg.pdf."},{"key":"e_1_2_1_67_1","unstructured":"Yahoo!. 2011. Yahoo! Webscope Dataset Anonymized Yahoo! Search Logs with Relevance Judgments Version 1.0. Retrieved from http:\/\/labs.yahoo.com\/Academic_Relations.  Yahoo!. 2011. Yahoo! Webscope Dataset Anonymized Yahoo! Search Logs with Relevance Judgments Version 1.0. Retrieved from http:\/\/labs.yahoo.com\/Academic_Relations."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448954"},{"volume-title":"Modeling Learning Impacts on Day-to-day Travel Choice","author":"Yanmaz-Tuzel Ozlem","key":"e_1_2_1_69_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-0820-9_19"},{"volume-title":"The New Palgrave Dictionary of Economics: Design of Experiments and Behavioral Economics","author":"Peyton Young H. H.","key":"e_1_2_1_70_1"},{"volume-title":"Strategic Learning and Its Limits","author":"Young H. Peyton","key":"e_1_2_1_71_1"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.028"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767761"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3351450","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3351450","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:51Z","timestamp":1750206351000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3351450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,8]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3351450"],"URL":"https:\/\/doi.org\/10.1145\/3351450","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2020,2,8]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}