Document listing on repetitive collections with guaranteed performance

Abstract

We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1, σ] is composed of D copies of a string of size n, and s single-character edits are applied on the copies. We introduce the first document listing index with size Õ(n+s), precisely O((n lg σ+s lg2 N) lg D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc strings where it appears in time O(m2 + m lg N(lgD + lgϵ N).