# Document Listing on Repetitive Collections with Guaranteed Performance

arXiv: https://arxiv.org/abs/1707.06374 · HTML: https://mlsanity.com/paper/1707.06374/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2017.

## Built on by (most cited first, 1 of 1)

- [Hybrid OCR-LLM Framework for Enterprise-Scale Document Information Extraction Under Copy-heavy Task](https://mlsanity.com/paper/2510.10138/) (2025)

## Abstract (arXiv)

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 edits are applied on ranges of copies. We introduce the first document listing index with size tildeO(n+s), precisely O((nlogσ+slog2 N)log D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc>0 strings where it appears in time O(mlog1+ε N · ndoc), for any constant ε>0 (and tells in time O(mlog N) if ndoc=0). Our technique is to augment a range data structure that is commonly used on grammar-based indexes, so that instead of retrieving all the pattern occurrences, it computes useful summaries on them. We show that the idea has independent interest: we introduce the first grammar-based index that, on a text T[1,N] with a grammar of size r, uses O(rlog N) bits and counts the number of occurrences of a pattern P[1,m] in time O(m2 + mlog2+ε r), for any constant ε>0. We also give the first index using O(zlog(N/z)log N) bits, where T is parsed by Lempel-Ziv into z phrases, counting occurrences in time O(mlog2+ε N).