LRM-trees: compressed indices, adaptive sorting, and compressed permutations

DOI10.1016/j.tcs.2012.08.010zbMath1252.68082OpenAlexW2175677593WikidataQ61661658 ScholiaQ61661658MaRDI QIDQ1758161

Jérémy Barbay, Gonzalo Navarro, Johannes Fischer

Publication date: 8 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.08.010

zbMATH Keywords

compressed data structuresrange minimum queriesadaptive sorting algorithmsdata structures for permutations

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (7)

Document listing on repetitive collections with guaranteed performance ⋮ On compressing permutations and adaptive sorting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Compressed range minimum queries ⋮ From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures ⋮ Inducing Suffix and LCP Arrays in External Memory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On compressing permutations and adaptive sorting
• Representing trees of higher degree
• Faster entropy-bounded compressed suffix trees
• Sorting shuffled monotone sequences
• A framework for adaptive sorting
• Partitioning permutations into increasing and decreasing subsequences
• The cell probe complexity of succinct data structures
• Optimal lower bounds for rank and select indexes
• Compressed representations of sequences and full-text indexes
• Alphabet Partitioning for Compressed Rank/Select and Applications
• Optimal Succinctness for Range Minimum Queries
• Squeezing succinct data structures into entropy bounds
• On Space Efficient Two Dimensional Range Minimum Data Structures
• Recursive Star-Tree Parallel Data Structure
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Practical Entropy-Compressed Rank/Select Dictionary
• COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
• A Method for the Construction of Minimum-Redundancy Codes
• Algorithms and Computation

This page was built for publication: LRM-trees: compressed indices, adaptive sorting, and compressed permutations