{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:05Z","timestamp":1750220045089,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"US NSF","doi-asserted-by":"crossref","award":["CCF\u20131017623 and CCF\u20131218904"],"award-info":[{"award-number":["CCF\u20131017623 and CCF\u20131218904"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            The ranked (or top-\n            <jats:italic>k<\/jats:italic>\n            ) document retrieval problem is defined as follows: preprocess a collection\n            <jats:italic>\n              {T\n              <jats:sub>1<\/jats:sub>\n              ,T\n              <jats:sub>2<\/jats:sub>\n              ,\u2026 ,T\n              <jats:sub>d<\/jats:sub>\n              }\n            <\/jats:italic>\n            of\n            <jats:italic>d<\/jats:italic>\n            strings (called documents) of total length\n            <jats:italic>n<\/jats:italic>\n            into a data structure, such that for any given query\n            <jats:italic>(P,k)<\/jats:italic>\n            , where\n            <jats:italic>P<\/jats:italic>\n            is a string (called pattern) of length\n            <jats:italic>p \u2265 1<\/jats:italic>\n            and\n            <jats:italic>k \u2208 [1,d]<\/jats:italic>\n            is an integer, the identifiers of those\n            <jats:italic>k<\/jats:italic>\n            documents that are most relevant to\n            <jats:italic>P<\/jats:italic>\n            can be reported, ideally in the sorted order of their relevance. The seminal work by Hon et\u00a0al. [FOCS 2009 and Journal of the ACM 2014] presented an\n            <jats:italic>O(n)<\/jats:italic>\n            -space (in words) data structure with\n            <jats:italic>O(p+k<\/jats:italic>\n            log\n            <jats:italic>k)<\/jats:italic>\n            query time. The query time was later improved to\n            <jats:italic>O(p+k)<\/jats:italic>\n            [SODA 2012] and further to\n            <jats:italic>O(p\/<\/jats:italic>\n            log\n            <jats:italic>\n              <jats:sub>\u03c3n+k<\/jats:sub>\n              )\n            <\/jats:italic>\n            [SIAM Journal on Computing 2017] by Navarro and Nekrich, where\n            <jats:italic>\u03c3<\/jats:italic>\n            is the alphabet size. We revisit this problem in the external memory model and present three data structures. The first one takes\n            <jats:italic>O(n)<\/jats:italic>\n            -space and answer queries in\n            <jats:italic>O(p\/B<\/jats:italic>\n            + log\n            <jats:italic>\n              <jats:sub>B<\/jats:sub>\n              n + k\/B+\n            <\/jats:italic>\n            log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>(n\/B)<\/jats:italic>\n            ) I\/Os, where\n            <jats:italic>B<\/jats:italic>\n            is the block size. The second one takes\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>(n\/B)<\/jats:italic>\n            ) space and answer queries in optimal\n            <jats:italic>O(p\/B<\/jats:italic>\n            + log\n            <jats:italic>\n              <jats:sub>B<\/jats:sub>\n              n + k\/B)\n            <\/jats:italic>\n            I\/Os. In both cases, the answers are reported in the unsorted order of relevance. To handle sorted top-\n            <jats:italic>k<\/jats:italic>\n            document retrieval, we present an\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:italic>(d\/B))<\/jats:italic>\n            space data structure with optimal query cost.\n          <\/jats:p>","DOI":"10.1145\/3559763","type":"journal-article","created":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T11:20:20Z","timestamp":1663845620000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Ranked Document Retrieval in External Memory"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2190-5840","authenticated-orcid":false,"given":"Rahul","family":"Shah","sequence":"first","affiliation":[{"name":"Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2656-6147","authenticated-orcid":false,"given":"Cheng","family":"Sheng","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Chinese University of Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6852-1035","authenticated-orcid":false,"given":"Sharma","family":"Thankachan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, North Carolina State University, Raleigh, North Carolina, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7970-6118","authenticated-orcid":false,"given":"Jeffrey","family":"Vitter","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, University of Mississippi, Oxford, Mississippi, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_4"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304010"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77614"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2019.9"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40273-9_22"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2590774"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.19"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.20"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Yossi Matias S. Muthukrishnan S\u00fcleyman Cenk Sahinalp and Jacob Ziv. 1998. Augmenting suffix trees with applications(ESA\u201998). Springer-Verlag London UK 67\u201378.","DOI":"10.1007\/3-540-68530-8_6"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.10.008"},{"key":"e_1_3_2_15_2","first-page":"657","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Muthukrishnan S.","year":"2002","unstructured":"S. Muthukrishnan. 2002. Efficient algorithms for document retrieval problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, David Eppstein (Ed.). ACM\/SIAM, 657\u2013666."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535933"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.84"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/140998949"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601073"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2543924"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009992"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594557"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_68"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.02.002"},{"key":"e_1_3_2_25_2","volume-title":"Lecture 1: External Memory Model and Sorting","author":"Tao Yufei","year":"2014","unstructured":"Yufei Tao. 2014. Lecture 1: External Memory Model and Sorting. Lecture Notes. Chinese University of Hong Kong."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559763","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:07:57Z","timestamp":1750183677000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3559763"],"URL":"https:\/\/doi.org\/10.1145\/3559763","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2020-05-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}