Ranked Document Retrieval in External Memory-猫眼课题宝

外部存储器中的排名文档检索

DOI：

10.1145/3559763

发表时间：

2023

期刊：

ACM Transactions on Algorithms

影响因子：

1.3

通讯作者：

中科院分区：

计算机科学3区

文献类型：

作者：

Shah, Rahul;Sheng, Cheng;Thankachan, Sharma;Vitter, Jeffrey

排序（或top-k）文档检索问题定义如下：将总长度为{T1，T2，…，Td}的字符串（称为文档）的集合预处理成一个数据结构，使得对于任何给定的查询（P,k），其中P是长度≥1的字符串（称为模式），k∈[1，d]是一个整数，可以报告与top1最相关的那些文档的标识符，理想情况下是按照它们的相关性排序。Hon等人的开创性工作[FOCS 2009和Journal of ACM 2014]提出了查询时间为o （p+klogk）的anO(n)空间（以单词表示）数据结构。查询时间后来由Navarro和Nekrich改进了toO(p+k)[SODA 2012]和toO(p/logσn+k)[SIAM Journal on Computing 2017]，其中σ为字母表大小。我们在外部存储器模型中重新讨论了这个问题，并提出了三种数据结构。第一个占用o (n)空间，并回答查询inO(p/B+ logBn + k/B+log*(n/B)) I/ o，其中bis是块大小。第二个占用o （nlog*(n/B)）空间，并以optimalO(p/B+ logBn + k/B)I/ o回答查询。在这两种情况下，答案都是以无序的相关性顺序报告的。为了处理排序的top-k文档检索，我们提出了查询成本最优的anO（nlog(d/B)）空间数据结构。

The ranked (or top-k) document retrieval problem is defined as follows: preprocess a collection{T1,T2,… ,Td}ofdstrings (called documents) of total lengthninto a data structure, such that for any given query(P,k), wherePis a string (called pattern) of lengthp ≥ 1andk ∈ [1,d]is an integer, the identifiers of thosekdocuments that are most relevant toPcan be reported, ideally in the sorted order of their relevance. The seminal work by Hon et al. [FOCS 2009 and Journal of the ACM 2014] presented anO(n)-space (in words) data structure withO(p+klogk)query time. The query time was later improved toO(p+k)[SODA 2012] and further toO(p/logσn+k)[SIAM Journal on Computing 2017] by Navarro and Nekrich, whereσis the alphabet size. We revisit this problem in the external memory model and present three data structures. The first one takesO(n)-space and answer queries inO(p/B+ logBn + k/B+log*(n/B)) I/Os, whereBis the block size. The second one takesO(nlog*(n/B)) space and answer queries in optimalO(p/B+ logBn + k/B)I/Os. In both cases, the answers are reported in the unsorted order of relevance. To handle sorted top-kdocument retrieval, we present anO(nlog(d/B))space data structure with optimal query cost.