Top-k Document Retrieval in Compressed Space

Let 𝓓 be a collection of D strings of total length n over an alphabet of size σ. We consider the so-called top-k document retrieval problem: given a short string P and an integer k, list the identifiers of k strings in 𝓓 most relevant to P, in decreasing order of relevance. Relevance may be a fixed value associated with the strings where P occurs, or the number of times P occurs in the strings. While RAM-optimal solutions using O (n log n ) bits and O (|P|/logσ n + k ) time exist, solving the problem optimally within space close to O (n log σ ) bits is open.