Space-Efficient Top-k Document Retrieval
Gonzalo Navarro and Daniel Valenzuela
Supporting top-k document retrieval queries on general text databases, that
is, finding the k documents where a given pattern occurs most frequently,
has
become a topic of interest with practical applications.
While the problem has been solved in
optimal time and linear space, the actual space usage is a serious concern. In
this paper we study various reduced-space structures that support top-k
retrieval and propose new alternatives. Our experimental results show
that our novel structures and algorithms dominate almost all the
space/time tradeoff.