{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T07:56:08Z","timestamp":1686124568179},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,4,29]],"date-time":"2016-04-29T00:00:00Z","timestamp":1461888000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003453","name":"Guangdong Natural Science Foundation","doi-asserted-by":"crossref","award":["S2013010016852"],"id":[{"id":"10.13039\/501100003453","id-type":"DOI","asserted-by":"crossref"}]},{"name":"BNU-HKBU United International College internal grant, and the National Natural Science Foundation of China","award":["61303180 and 61573163"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"We present Q2P, a system that discovers query templates from search engines via their query autocompletion services. Q2P is distinct from the existing works in that it does not rely on query logs of search engines that are typically not readily available. Q2P is also unique in that it uses a trie to economically store queries sampled from a search engine and employs a beam-search strategy that focuses the expansion of the trie on its most promising nodes. Furthermore, Q2P leverages the trie-based storage of query sample to discover query templates using only two passes over the trie. Q2P is a key part of our ongoing project Deep2Q on a template-driven data integration on the Deep Web, where the templates learned by Q2P are used to guide the integration process in Deep2Q. Experimental results on four major search engines indicate that (1) Q2P sends only a moderate number of queries (ranging from 597 to 1,135) to the engines, while obtaining a significant number of completions per query (ranging from 4.2 to 8.5 on the average); (2) a significant number of templates (ranging from 8 to 32 when the minimum support for frequent templates is set to 1%) may be discovered from the samples.<\/jats:p>","DOI":"10.1145\/2873061","type":"journal-article","created":{"date-parts":[[2016,5,2]],"date-time":"2016-05-02T12:16:07Z","timestamp":1462191367000},"page":"1-29","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Q2P"],"prefix":"10.1145","volume":"10","author":[{"given":"Wensheng","family":"Wu","sequence":"first","affiliation":[{"name":"University of Southern California, Los Angeles, CA"}]},{"given":"Weiyi","family":"Meng","sequence":"additional","affiliation":[{"name":"State University of New York at Binghamton, Binghamton, NY"}]},{"given":"Weifeng","family":"Su","sequence":"additional","affiliation":[{"name":"BNU-HKBU United International College, China, ZhuHai, China"}]},{"given":"Guangyou","family":"Zhou","sequence":"additional","affiliation":[{"name":"Central China Normal University, China, WuHan, China"}]},{"given":"Yao-Yi","family":"Chiang","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, CA"}]}],"member":"320","published-online":{"date-parts":[[2016,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772692"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655281"},{"key":"e_1_2_1_3_1","unstructured":"Amazon. 2014. Amazon Autocompletion API. Retrieved from http:\/\/completion.amazon.com\/search\/complete?method=completion&search-alias==aps&client==amazon-search-ui&mkt==1&x==updateISSCompletion& sc==1&noCacheIE==1294493634389&q=={query}. Amazon. 2014. Amazon Autocompletion API. Retrieved from http:\/\/completion.amazon.com\/search\/complete?method=completion&search-alias==aps&client==amazon-search-ui&mkt==1&x==updateISSCompletion& sc==1&noCacheIE==1294493634389&q=={query}."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453868"},{"key":"e_1_2_1_5_1","unstructured":"Bing. 2014. Bing Autocompletion API. Retrieved from http:\/\/api.search.live.com\/osjson.aspx?query={query}. Bing. 2014. Bing Autocompletion API. Retrieved from http:\/\/api.search.live.com\/osjson.aspx?query={query}."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559857"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376702"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007612"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375731"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"AnHai Doan Alon Halevy and Zazhary Ives. 2012. Principles of Data Integration. Morgan Kaufmann. AnHai Doan Alon Halevy and Zazhary Ives. 2012. Principles of Data Integration. Morgan Kaufmann.","DOI":"10.1016\/B978-0-12-416044-6.00015-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090488.1090497"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687620"},{"key":"e_1_2_1_13_1","volume-title":"Yu","author":"Dragut Eduard C.","year":"2012","unstructured":"Eduard C. Dragut , Weiyi Meng , and Clement T . Yu . 2012 . Deep Web Query Interface Understanding and Integration. Morgan & Claypool Publishers . Eduard C. Dragut, Weiyi Meng, and Clement T. Yu. 2012. Deep Web Query Interface Understanding and Integration. Morgan & Claypool Publishers."},{"key":"e_1_2_1_14_1","unstructured":"Google. 2014. Google Autocompletion API. Retrieved from http:\/\/google.com\/complete\/search?output=firefox& q=={query}. Google. 2014. Google Autocompletion API. Retrieved from http:\/\/google.com\/complete\/search?output=firefox& q=={query}."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733836_1"},{"key":"e_1_2_1_16_1","volume-title":"Ordille","author":"Halevy Alon Y.","year":"2006","unstructured":"Alon Y. Halevy , Anand Rajaraman , and Joann J . Ordille . 2006 b. Data integration: The teenage years. In Proc. of VLDB. 9--16. Alon Y. Halevy, Anand Rajaraman, and Joann J. Ordille. 2006b. Data integration: The teenage years. In Proc. of VLDB. 9--16."},{"key":"e_1_2_1_17_1","volume-title":"4th Biennial Conference on Innovative Data Systems Research (CIDR’\u201909)","author":"Ives Zachary G.","year":"2009","unstructured":"Zachary G. Ives , Craig A. Knoblock , Steven Minton , Marie Jacob , Partha Pratim Talukdar , Rattapoom Tuchinda , Jos\u00e9 Luis Ambite , Maria Muslea , and Cenk Gazen . 2009 . Interactive data integration through smart copy & paste . In 4th Biennial Conference on Innovative Data Systems Research (CIDR’\u201909) , Online Proceedings. http:\/\/www-db.cs.wisc.edu\/cidr\/cidr 2009\/Paper_71.pdf. Zachary G. Ives, Craig A. Knoblock, Steven Minton, Marie Jacob, Partha Pratim Talukdar, Rattapoom Tuchinda, Jos\u00e9 Luis Ambite, Maria Muslea, and Cenk Gazen. 2009. Interactive data integration through smart copy & paste. In 4th Biennial Conference on Innovative Data Systems Research (CIDR’\u201909), Online Proceedings. http:\/\/www-db.cs.wisc.edu\/cidr\/cidr2009\/Paper_71.pdf."},{"key":"e_1_2_1_18_1","first-page":"19","article-title":"Adaptive query processing for internet applications","volume":"23","author":"Ives Zachary G.","year":"2000","unstructured":"Zachary G. Ives , Alon Y. Levy , Daniel S. Weld , Daniela Florescu , and Marc Friedman . 2000 . Adaptive query processing for internet applications . IEEE Data Eng. Bull. 23 , 2 (2000), 19 -- 26 . Zachary G. Ives, Alon Y. Levy, Daniel S. Weld, Daniela Florescu, and Marc Friedman. 2000. Adaptive query processing for internet applications. IEEE Data Eng. Bull. 23, 2 (2000), 19--26.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376701"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989381"},{"key":"e_1_2_1_21_1","first-page":"1099","article-title":"Randomized generalization for aggregate suppression over hidden web databases","volume":"4","author":"Jin Xin","year":"2011","unstructured":"Xin Jin , Nan Zhang , Aditya Mone , and Gautam Das . 2011 b. Randomized generalization for aggregate suppression over hidden web databases . PVLDB 4 , 11 (2011), 1099 -- 1110 . Xin Jin, Nan Zhang, Aditya Mone, and Gautam Das. 2011b. Randomized generalization for aggregate suppression over hidden web databases. PVLDB 4, 11 (2011), 1099--1110.","journal-title":"PVLDB"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860708"},{"key":"e_1_2_1_23_1","volume-title":"Proc. of ACL. 1337--1345","author":"Li Xiao","year":"2010","unstructured":"Xiao Li . 2010 . Understanding the semantic structure of noun phrase queries . In Proc. of ACL. 1337--1345 . Xiao Li. 2010. Understanding the semantic structure of noun phrase queries. In Proc. of ACL. 1337--1345."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.39"},{"key":"e_1_2_1_25_1","volume-title":"Proc. of CIDR. 342--350","author":"Madhavan Jayant","year":"2007","unstructured":"Jayant Madhavan , Shirley Cohen , Xin Luna Dong , Alon Y. Halevy , Shawn R. Jeffery , David Ko , and Cong Yu . 2007 . Web-scale data integration: You can afford to pay as you go . In Proc. of CIDR. 342--350 . Jayant Madhavan, Shirley Cohen, Xin Luna Dong, Alon Y. Halevy, Shawn R. Jeffery, David Ko, and Cong Yu. 2007. Web-scale data integration: You can afford to pay as you go. In Proc. of CIDR. 342--350."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454163"},{"key":"e_1_2_1_27_1","volume-title":"Proc. of VLDB. 219--230","author":"Nandi Arnab","unstructured":"Arnab Nandi and H. V. Jagadish . 2007. Effective phrase prediction . In Proc. of VLDB. 219--230 . Arnab Nandi and H. V. Jagadish. 2007. Effective phrase prediction. In Proc. of VLDB. 219--230."},{"key":"e_1_2_1_28_1","volume-title":"Proc. of CIDR.","author":"Nandi Arnab","unstructured":"Arnab Nandi and H. V. Jagadish . 2009. Qunits: Queried units in database search . In Proc. of CIDR. Arnab Nandi and H. V. Jagadish. 2009. Qunits: Queried units in database search. In Proc. of CIDR."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187892"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_2_1_31_1","volume-title":"Proc. of ICDE. 215--224","author":"Pei Jian","year":"2001","unstructured":"Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , and Meichun Hsu . 2001 . PrefixSpan: Mining sequential patterns by prefix-projected growth . In Proc. of ICDE. 215--224 . Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, and Meichun Hsu. 2001. PrefixSpan: Mining sequential patterns by prefix-projected growth. In Proc. of ICDE. 215--224."},{"key":"e_1_2_1_32_1","volume-title":"Proc. of VLDB. 129--138","author":"Raghavan Sriram","year":"2001","unstructured":"Sriram Raghavan and Hector Garcia-Molina . 2001 . Crawling the hidden web . In Proc. of VLDB. 129--138 . Sriram Raghavan and Hector Garcia-Molina. 2001. Crawling the hidden web. In Proc. of VLDB. 129--138."},{"key":"e_1_2_1_33_1","volume-title":"Russell and Peter Norvig","author":"Stuart","year":"2010","unstructured":"Stuart J. Russell and Peter Norvig . 2010 . Artificial Intelligence\u2014A Modern Approach. Pearson Education. I--XVIII , 1--1132 pages. Stuart J. Russell and Peter Norvig. 2010. Artificial Intelligence\u2014A Modern Approach. Pearson Education. I--XVIII, 1--1132 pages."},{"key":"e_1_2_1_34_1","volume-title":"Proc. of VLDB. 663--674","author":"Vaz Salles Marcos Antonio","year":"2007","unstructured":"Marcos Antonio Vaz Salles , Jens-Peter Dittrich , Shant Kirakos Karakashian , Olivier Ren\u00e9 Girard , and Lukas Blunschi . 2007 . iTrails: Pay-as-you-go information integration in dataspaces . In Proc. of VLDB. 663--674 . Marcos Antonio Vaz Salles, Jens-Peter Dittrich, Shant Kirakos Karakashian, Olivier Ren\u00e9 Girard, and Lukas Blunschi. 2007. iTrails: Pay-as-you-go information integration in dataspaces. In Proc. of VLDB. 663--674."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350232"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807211"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.124"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512405.2512408"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452394"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2487854"},{"key":"e_1_2_1_41_1","unstructured":"Yahoo! 2014. Yahoo! Autocompletion API. Retrieved fcrom http:\/\/ff.search.yahoo.com\/gossip?output=fxjson&command=={query}. Yahoo! 2014. Yahoo! Autocompletion API. Retrieved fcrom http:\/\/ff.search.yahoo.com\/gossip?output=fxjson&command=={query}."}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2873061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T06:55:30Z","timestamp":1672469730000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2873061"}},"subtitle":["Discovering Query Templates via Autocompletion"],"short-title":[],"issued":{"date-parts":[[2016,4,29]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,25]]}},"alternative-id":["10.1145\/2873061"],"URL":"https:\/\/doi.org\/10.1145\/2873061","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,29]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}