On compressing permutations and adaptive sorting
From MaRDI portal
Publication:391981
DOI10.1016/j.tcs.2013.10.019zbMath1358.68079arXiv1108.4408OpenAlexW2147996100MaRDI QIDQ391981
Gonzalo Navarro, Jérémy Barbay
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.4408
Searching and sorting (68P10) Permutations, words, matrices (05A05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (9)
Grammar compressed sequences with rank/select support ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Wavelet trees for all ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Efficient fully-compressed sequence representations ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ Unnamed Item ⋮ Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Succinct representations of permutations and functions
- Untangled monotonic chains and adaptive range search
- On computing the length of longest increasing subsequences
- An almost optimal algorithm for unbounded searching
- Sorting shuffled monotone sequences
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Approximate string matching with compressed indexes
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Approximating minimum cocolorings.
- Partitioning permutations into increasing and decreasing subsequences
- Stronger Lempel-Ziv based compressed text indexing
- Rank and select revisited and extended
- Optimal lower bounds for rank and select indexes
- From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures
- Compressed representations of sequences and full-text indexes
- Alphabet Partitioning for Compressed Rank/Select and Applications
- Succinct indexes for strings, binary relations and multilabeled trees
- Measures of Presortedness and Optimal Sorting Algorithms
- On the Redundancy of Succinct Data Structures
- Optimal Succinctness for Range Minimum Queries
- Rank/select operations on large alphabets
- Self-adjusting binary search trees
- Sorting and Searching in Multisets
- New text indexing functionalities of the compressed suffix arrays
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- A Method for the Construction of Minimum-Redundancy Codes
- Bounding the inefficiency of length-restricted prefix codes
This page was built for publication: On compressing permutations and adaptive sorting
