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

DOI10.1007/978-3-642-40273-9_8zbMath1394.68089MaRDI 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

sorting; permutation; unbounded search; compressed data structures; set union; adaptive (analysis of) algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

68P05: Data structures

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