Ranked document retrieval for multiple patterns

For the above two queries, we provide a linear space index with O(|P|+|Q|+nk) query time, under some standard relevance functions such as PageRank and TermFrequency. The document listing version of the above two problems asks to report all t documents that either contain P, but not Q, or contain both P and Q, depending on the query type. As a corollary of the top-k result, we obtain a linear space and O(|P|+|Q|+nt) query time solution for the document listing problems. We conjecture that any significant improvement over these results is highly unlikely. We also consider the scenario when the query consists of more than two patterns. Finally, we present space-efficient indexes for these problems.