On optimal top-k string retrieval

Let D = {d1, d2, d3,..., dD} be a given set of D (string) docu-ments of total length n. The top-k document retrieval prob-lem is to index D such that when a pattern P of length p, and a parameter k come as a query, the index returns the k most relevant documents to the pattern P. Hon et. al. [13] gave the first linear space framework to solve this problem in O(p + k log k) time. This was improved by Navarro and Nekrich [23] to O(p+ k). These results are powerful enough to support arbitrary relevance functions like frequency, prox-imity, PageRank, etc. In many applications like desktop or email search, the data resides on disk and hence disk-bound indexes are needed. Despite of continued progress on this problem in terms of theoretical, practical and compression aspects, any non-trivial bounds in external memory model have so far been elusive. Internal memory (or RAM) so-lution to this problem decomposes the problem into O(p) subproblems and thus incurs the additive factor of O(p). In external memory, these approaches will lead to O(p) I/Os instead of optimal O(p/B) I/O term where B is the block-size. We re-interpret the problem independent of p, as inter-val stabbing with priority over tree-shaped structure. This leads us to a linear space index in external memory sup-porting top-k queries (with unsorted outputs) in near op-timal O(p/B + logB n + log (h) n + k/B) I/Os for any con-stant h1. Then we get O(n log ∗ n) space index with optimal O(p/B+logB n+k/B) I/Os. As a corollary, we also show the result in RAM which allows sorted order retrieval in O(k) time, if the locus of pattern match is provided in advance. This gives optimal performance in many applications where finding the locus of pattern in a suffix tree can be done much faster than usual O(p)