Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Document Listing for Queries with Excluded Pattern
verfasst von : Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let $\mathcal D$ = {d1,d2,...,d D } be a given collection of D string documents of total length n. We consider the problem of indexing $\mathcal D$ such that, whenever two patterns P + and P− comes as an online query, we can list all those documents containing P + butnotP−. Let t represent the number of such documents. An index proposed by Fischer et al. (LATIN, 2012) can answer this query in $O(|P^+|+|P^-|+t+\sqrt{n})$ time. However, its space requirement is O(n3/2) bits. We propose the first linear-space index for this problem with a worst case query time of $O(|P^+|+|P^-|+\sqrt{n}\log \log n+\sqrt{nt}\log^{2.5} n)$.