Linear time construction of compressed text indices in compact space
From MaRDI portal
Publication:5259552
DOI10.1145/2591796.2591885zbMath1315.68110arXiv1401.0936OpenAlexW1988110322MaRDI QIDQ5259552
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
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)
Related Items (16)
Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended ⋮ A framework for space-efficient string kernels ⋮ Unnamed Item ⋮ Space-efficient construction of compressed suffix trees ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ Lightweight BWT and LCP Merging via the Gap Algorithm ⋮ Burrows-Wheeler transform and LCP array construction in constant space ⋮ Flexible indexing of repetitive collections ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Lightweight merging of compressed indices based on BWT variants ⋮ Space-efficient computation of the LCP array from the Burrows-Wheeler transform ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- 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
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
This page was built for publication: Linear time construction of compressed text indices in compact space
