From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures

DOI10.1007/978-3-642-40273-9_8zbMath1394.68089OpenAlexW829492447MaRDI QIDQ2848970

Jérémy Barbay

Publication date: 13 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_8

zbMATH Keywords

sortingpermutationunbounded searchcompressed data structuresset unionadaptive (analysis of) algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Data structures (68P05)

Related Items

On compressing permutations and adaptive sorting ⋮ Adaptive succinctness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct representations of permutations and functions
• Efficient fully-compressed sequence representations
• An almost optimal algorithm for unbounded searching
• Sorting shuffled monotone sequences
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• A framework for adaptive sorting
• Sublinear merging and natural mergesort
• Optimal lower bounds for rank and select indexes
• Alphabet-Independent Compressed Text Indexing
• Succinct indexes for strings, binary relations and multilabeled trees
• Measures of Presortedness and Optimal Sorting Algorithms
• Sorting, trees, and measures of order
• Optimal Succinctness for Range Minimum Queries
• Rank/select operations on large alphabets
• Optimal Lower Bounds for Rank and Select Indexes
• Two Probabilistic Results on Merging
• Universal codeword sets and representations of the integers
• Sorting and Searching in Multisets
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Algorithms and Computation
• Combinatorial Pattern Matching
• COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets