{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,8]],"date-time":"2023-09-08T00:07:15Z","timestamp":1694131635164},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            Natural language text corpora are often available as sets of syntactically parsed trees. A wide range of expressive tree queries are possible over such parsed trees that open a new avenue in searching over natural language text. They not only allow for querying roles and relationships within sentences, but also improve search effectiveness compared to flat keyword queries. One major drawback of current systems supporting querying over parsed text is the performance of evaluating queries over large data. In this paper we propose a novel indexing scheme over unique subtrees as index keys. We also propose a novel\n            <jats:italic>root-split<\/jats:italic>\n            coding scheme that stores subtree structural information only partially, thus reducing index size and improving querying performance. Our extensive set of experiments show that\n            <jats:italic>root-split<\/jats:italic>\n            coding reduces the index size of any interval coding which stores individual node numbers by a factor of 50% to 80%, depending on the sizes of subtrees indexed. Moreover, We show that our index using\n            <jats:italic>root-split<\/jats:italic>\n            coding, outperforms previous approaches by at least an order of magnitude in terms of the response time of queries.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350249","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1316-1327","source":"Crossref","is-referenced-by-count":5,"title":["Efficient indexing and querying over syntactically annotated trees"],"prefix":"10.14778","volume":"5","author":[{"given":"Pirooz","family":"Chubak","sequence":"first","affiliation":[{"name":"University of Alberta"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davood","family":"Rafiei","sequence":"additional","affiliation":[{"name":"University of Alberta"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879022"},{"key":"e_1_2_1_2_1","unstructured":"The aquaint corpus of english news text 2002. http:\/\/www.ldc.upenn.edu\/Catalog\/docs\/LDC2002T31\/.  The aquaint corpus of english news text 2002. http:\/\/www.ldc.upenn.edu\/Catalog\/docs\/LDC2002T31\/."},{"key":"e_1_2_1_3_1","first-page":"2670","volume-title":"IJCAI","author":"Banko M.","year":"2007","unstructured":"M. Banko , M. Cafarella , S. Soderland , M. Broadhead , and O. Etzioni . Open Information Extraction from the Web . In IJCAI , pages 2670 -- 2676 , 2007 . M. Banko, M. Cafarella, S. Soderland, M. Broadhead, and O. Etzioni. Open Information Extraction from the Web. In IJCAI, pages 2670--2676, 2007."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.48"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_6_1","first-page":"52","volume-title":"NAACL","author":"Christensen J.","year":"2010","unstructured":"J. Christensen , Mausam, S. Soderland , and E. Etzioni . Semantic Role Labeling for Open Information Extraction . In NAACL , pages 52 -- 60 , 2010 . J. Christensen, Mausam, S. Soderland, and E. Etzioni. Semantic Role Labeling for Open Information Extraction. In NAACL, pages 52--60, 2010."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1060"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.3115\/1075096.1075150"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/502115.502117"},{"key":"e_1_2_1_11_1","first-page":"388","volume-title":"TREC","author":"Moldovan D.","year":"2002","unstructured":"D. Moldovan , S. Harabagiu , R. Girju , P. Morarescu , F. Lacatusu , A. Novischi , A. Badulescu , and O. Bolohan . LCC Tools for Question Answering . In TREC , pages 388 -- 397 , 2002 . D. Moldovan, S. Harabagiu, R. Girju, P. Morarescu, F. Lacatusu, A. Novischi, A. Badulescu, and O. Bolohan. LCC Tools for Question Answering. In TREC, pages 388--397, 2002."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_2_1_13_1","volume-title":"CorpusSearch Users Manual","author":"Randall B.","year":"2000","unstructured":"B. Randall . CorpusSearch Users Manual . University of Pennsylvania , 2000 . http:\/\/www.ling.upenn.edu\/~dringe\/CorpStuff\/Manual\/Contents.html. B. Randall. CorpusSearch Users Manual. University of Pennsylvania, 2000. http:\/\/www.ling.upenn.edu\/~dringe\/CorpStuff\/Manual\/Contents.html."},{"key":"e_1_2_1_14_1","volume-title":"TGrep2 User Manual version 1.15","author":"Rohde D.","year":"2005","unstructured":"D. Rohde . TGrep2 User Manual version 1.15 . Massachusetts Institute of Technology . http:\/\/tedlab.mit.edu\/dr\/Tgrep2, 2005 . D. Rohde. TGrep2 User Manual version 1.15. Massachusetts Institute of Technology. http:\/\/tedlab.mit.edu\/dr\/Tgrep2, 2005."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2002.1029709"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368956"},{"key":"e_1_2_1_18_1","first-page":"118","volume-title":"ACL","author":"Wu F.","year":"2010","unstructured":"F. Wu and D. Weld . Open Information Extraction Using Wikipedia . In ACL , pages 118 -- 127 , 2010 . F. Wu and D. Weld. Open Information Extraction Using Wikipedia. In ACL, pages 118--127, 2010."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/383034.383038"},{"key":"e_1_2_1_21_1","volume-title":"A Simple Proof of the Inequality FFD(L) \u2264 11\/9 OPT(L)+1, &forall","author":"Yue M.","year":"1991","unstructured":"M. Yue . A Simple Proof of the Inequality FFD(L) \u2264 11\/9 OPT(L)+1, &forall ; L for the FFD Bin-Packing Algorithm. Acta Mathematicae Applicatae Sinica (English Series) , 7(4):321--331, 1991 . M. Yue. A Simple Proof of the Inequality FFD(L) \u2264 11\/9 OPT(L)+1, &forall; L for the FFD Bin-Packing Algorithm. Acta Mathematicae Applicatae Sinica (English Series), 7(4):321--331, 1991."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375722"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368955"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:27:43Z","timestamp":1672226863000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":22,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350249"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350249","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}