Linear time construction of compressed text indices in compact space

DOI10.1145/2591796.2591885zbMATH Open1315.68110arXiv1401.0936OpenAlexW1988110322MaRDI QIDQ5259552FDOQ5259552

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)

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.

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

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

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)

Cites Work

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

Cited In (24)

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

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)