Linear time construction of compressed text indices in compact space

DOI10.1145/2591796.2591885MaRDI QIDQ5259552zbMATHOpenAlexFDO

Authors Djamal Belazzougui

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0936

zbMATH Keywords

pattern matchingtext indexingsuccinct space

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Computing methodologies for text processing; mathematical typography (68U15)

Abstract: We show that the compressed suffix array and the compressed suffix tree for a string of length $n$ over an integer alphabet of size $sigmaleqn$ can both be built in $O(n)$ (randomized) time using only $O(nlogsigma)$ bits of working space. The previously fastest construction algorithms that used $O(nlogsigma)$ bits of space took times $O(nloglogsigma)$ and $O(nlo{g}^{epsilon}n)$ respectively (where $epsilon$ is any positive constant smaller than $1$). In the passing, we show that the Burrows-Wheeler transform of a string of length $n$ over an alphabet of size $sigma$ can be built in deterministic $O(n)$ time and space $O(nlogsigma)$. We also show that within the same time and space, we can carry many sequence analysis tasks and construct some variants of the compressed suffix array and compressed suffix tree.

Recommendations

• Space-efficient construction of compressed indexes in deterministic linear time
• Fast compressed self-indexes with deterministic linear-time construction
• Combinatorial Pattern Matching
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(23)

• Greedy shortest common superstring approximation in compact space
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Fast compressed self-indexes with deterministic linear-time construction
• Parallel computation of the Burrows Wheeler transform in compact space
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• Space-efficient construction of compressed indexes in deterministic linear time
• External memory BWT and LCP computation for sequence collections with applications
• scientific article; zbMATH DE number 7559178 (Why is no real title available?)
• Lightweight BWT and LCP merging via the gap algorithm
• Combinatorial Pattern Matching
• Space-efficient construction of compressed suffix trees
• Lempel-Ziv factorization powered by space efficient suffix trees
• Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
• Computing the Burrows-Wheeler transform in place and in small space
• Breaking a time-and-space barrier in constructing full-text indices
• scientific article; zbMATH DE number 7378722 (Why is no real title available?)
• Lightweight merging of compressed indices based on BWT variants
• Burrows-Wheeler transform and LCP array construction in constant space
• Flexible indexing of repetitive collections
• Algorithms and Computation
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Space-efficient parallel construction of succinct representations of suffix tree topologies

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Linear time construction of compressed text indices in compact space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259552)