2006/10/03 by Daniel Lemire, Owen Kaser, Lemire, Daniel +1
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Computation and Language (cs.CL) #Databases (cs.DB) #FOS: Computer and information sciences #cs.CL #cs.DB #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0610010
Fixed a typo
openalex publication_date 2006/10/03 · arxiv created 2014/02/04 · arxiv updated 2014/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In multimedia, text or bioinformatics databases, applications query sequences of n consecutive symbols called n-grams. Estimating the number of distinct n-grams is a view-size estimation problem. While view sizes can be estimated by sampling under statistical assumptions, we desire an unassuming algorithm with universally valid accuracy bounds. Most related work has focused on repeatedly hashing the data, which is prohibitive for large data sources. We prove that a one-pass one-hash algorithm is sufficient for accurate estimates if the hashing is sufficiently independent. To reduce costs further, we investigate recursive random hashing algorithms and show that they are sufficiently independent in practice. We compare our running times with exact counts using suffix arrays and show that, while we use hardly any storage, we are an order of magnitude faster. The approach further is extended to a one-pass/one-hash computation of n-gram entropy and iceberg counts. The experiments use a large collection of English text from the Gutenberg Project as well as synthetic data.