Abstract
Let {d <sub>1</sub> ,d <sub>2</sub> ,...d <sub>D</sub> } be a given set of D string documents of total length n, our task is to index , such that the k most relevant documents for an online query pattern P of length p can be retrieved efficiently. We propose an index of size |CSA| + nlogD(2 + o(1)) bits and O(t <sub>s</sub> (p) + kloglogn + polyloglogn) query time for the basic relevance metric term-frequency, where |CSA| is the size (in bits) of a compressed full text index of , with O(t <sub>s</sub> (p)) time for searching a pattern of length p. We further reduce the space to |CSA| + nlogD(1 + o(1)) bits, however the query time will be O(t <sub>s</sub> (p) + k(logσloglogn) <sup>1 + ε</sup> + polyloglogn), where σ is the alphabet size and ε > 0 is any constant. © 2012 Springer-Verlag.