{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:07:11Z","timestamp":1775282831840,"version":"3.50.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0934322"],"award-info":[{"award-number":["CNS-0934322"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Center for Intelligent Information Retrieval"},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0844226"],"award-info":[{"award-number":["IIS-0844226"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Formulating and processing phrases and other term dependencies to improve query effectiveness is an important problem in information retrieval. However, accessing word-sequence statistics using inverted indexes requires unreasonable processing time or substantial space overhead. Establishing a balance between these competing space and time trade-offs can dramatically improve system performance.<\/jats:p>\n          <jats:p>\n            In this article, we present and analyze a new index structure designed to improve query efficiency in dependency retrieval models. By adapting a class of (\n            <jats:italic>\u03b5, \u03b4<\/jats:italic>\n            )-approximation algorithms originally proposed for sketch summarization in networking applications, we show how to accurately estimate statistics important in term-dependency models with low, probabilistically bounded error rates. The space requirements for the vocabulary of the index is only logarithmically linked to the size of the vocabulary.\n          <\/jats:p>\n          <jats:p>\n            Empirically, we show that the sketch index can reduce the space requirements of the vocabulary component of an index of\n            <jats:italic>n<\/jats:italic>\n            -grams consisting of between 1 and 4 words extracted from the GOV2 collection to less than 0.01% of the space requirements of the vocabulary of a full index. We also show that larger\n            <jats:italic>n<\/jats:italic>\n            -gram queries can be processed considerably more efficiently than in current alternatives, such as positional and next-word indexes.\n          <\/jats:p>","DOI":"10.1145\/2559168","type":"journal-article","created":{"date-parts":[[2014,1,28]],"date-time":"2014-01-28T13:49:22Z","timestamp":1390916962000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Indexing Word Sequences for Ranked Retrieval"],"prefix":"10.1145","volume":"32","author":[{"given":"Samuel","family":"Huston","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Shane","family":"Culpepper","sequence":"additional","affiliation":[{"name":"RMIT University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W. Bruce","family":"Croft","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390419"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348283.2348408"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718492"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). 819--826","author":"Bergsma S."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559819"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2005.11.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094072.2094077"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148285"},{"key":"e_1_2_1_11_1","volume-title":"Information Retrieval: Implementing and Evaluating Search Engines","author":"B\u00fcttcher S.","year":"2010"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"2380","author":"Charikar M."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 6th Symposium on Theoretical Informatics (Latin). Lecture Notes in Computer Science","volume":"2976","author":"Cormode G."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 5th SIAM International Conference on Data Mining (SDM).","author":"Cormode G."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_18_1","unstructured":"W. B. Croft and J. Callan. 2013. The Lemur Project. http:\/\/www.lemurproject.org\/.  W. B. Croft and J. Callan. 2013. The Lemur Project. http:\/\/www.lemurproject.org\/."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 18th Annual Symposium on Algorithms (ESA). Lecture Notes in Computer Science","volume":"6347","author":"Culpepper J. S."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 16th Australasian Document Computing Symposium (ADCS). 18--25","author":"Culpepper J. S."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348283.2348317"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2010048"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/964725.633056"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094072.2094073"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402756"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 9th International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science","volume":"2992","author":"Ganguly S."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). 250--261","author":"Goyal Amit","year":"2011"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). 1093--1103","author":"Goyal Amit","year":"2012"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390400"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526719"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2011.03.007"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.19"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_14"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935857"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398533"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-34963-1_12"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037661.2037662"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484028.2484096"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1572106"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076115"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 657--666","author":"Muthukrishnan S.","year":"2002"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_27"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2010.12.007"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063585"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009992"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277937"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291008"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242471.1242472"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.011"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390432"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871655"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277774"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the Large-Scale Distributed Systems for Information Retrieval Workshop. 33--37","author":"Tonellotto N."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89097-3_20"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1877766.1877768"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(95)00020-H"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009934"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 10th Australasian Document Computing Symposium (ADCS). 26--33","author":"Webber W."},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 10th Australasian Database Conference (ADC). 141--152","author":"Williams H. E."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028099.1028102"},{"key":"e_1_2_1_63_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann.","author":"Witten I. H.","year":"1999"},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of SIGIR Workshop on Query Representation and Understanding. 9--12","author":"Xue X."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559168","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:12Z","timestamp":1750230072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2559168"],"URL":"https:\/\/doi.org\/10.1145\/2559168","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2013-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}