Top-k Document Retrieval in External Memory
Top-k Document Retrieval in External Memory
复制标题
外部存储器中的 Top-k 文档检索
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Vitter
中科院分区：
文献类型：
--
作者：
Rahul Shah;Cheng Sheng;Sharma V. Thankachan;J. Vitter
令 ({cal{D}}) 为总长度为 n 的给定（字符串）文档集。 top-k 文档检索问题是索引 (cal{D})，使得当长度为 p 的模式 P 和参数 k 作为查询时，索引返回与 P 最相关的 k 个文档。我们提出了第一个非平凡的外部存储器索引，支持最佳 O(p/B + log B n + k/B) I/O 中的 top-k 文档检索查询，其中 B 是块大小。索引空间几乎是线性的 O(nlog* n) 个字。
Let ({cal{D}}) be a given set of (string) documents of total length n. The top-k document retrieval problem is to index (cal{D}) such that when a pattern P of length p, and a parameter k come as a query, the index returns those k documents which are most relevant to P. We present the first non-trivial external memory index supporting top-k document retrieval queries in optimal O(p/B + log B n + k/B) I/Os, where B is the block size. The index space is almost linear O(nlog* n) words.