Abstract
Let = {d 1 ,d 2 ,...,d D } be a given collection of D string documents of total length n. We consider the problem of indexing such that, whenever two patterns P + and P - comes as an online query, we can list all those documents containing P + but not P - . Let t represent the number of such documents. An index proposed by Fischer et al. (LATIN, 2012) can answer this query in time. However, its space requirement is O(n 3/2 ) bits. We propose the first linear-space index for this problem with a worst case query time of . © 2012 Springer-Verlag.