Succinct representations of permutations and functions
From MaRDI portal
Abstract: We investigate the problem of succinctly representing an arbitrary permutation, pi, on {0,...,n-1} so that pi^k(i) can be computed quickly for any i and any (positive or negative) integer power k. A representation taking (1+epsilon) n lg n + O(1) bits suffices to compute arbitrary powers in constant time, for any positive constant epsilon <= 1. A representation taking the optimal ceil{lg n!} + o(n) bits can be used to compute arbitrary powers in O(lg n / lg lg n) time. We then consider the more general problem of succinctly representing an arbitrary function, f: [n]
ightarrow [n] so that f^k(i) can be computed quickly for any i and any integer power k. We give a representation that takes (1+epsilon) n lg n + O(1) bits, for any positive constant epsilon <= 1, and computes arbitrary positive powers in constant time. It can also be used to compute f^k(i), for any negative integer k, in optimal O(1+|f^k(i)|) time. We place emphasis on the redundancy, or the space beyond the information-theoretic lower bound that the data structure uses in order to support operations efficiently. A number of lower bounds have recently been shown on the redundancy of data structures. These lower bounds confirm the space-time optimality of some of our solutions. Furthermore, the redundancy of one of our structures "surpasses" a recent lower bound by Golynski [Golynski, SODA 2009], thus demonstrating the limitations of this lower bound.
Recommendations
Cites work
- scientific article; zbMATH DE number 1670815 (Why is no real title available?)
- scientific article; zbMATH DE number 2086252 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 177536 (Why is no real title available?)
- scientific article; zbMATH DE number 512871 (Why is no real title available?)
- scientific article; zbMATH DE number 2038722 (Why is no real title available?)
- scientific article; zbMATH DE number 1830749 (Why is no real title available?)
- scientific article; zbMATH DE number 1830754 (Why is no real title available?)
- A categorization theorem on suffix arrays with applications to space efficient text indexes
- A cryptanalytic time-memory trade-off
- A simple optimal representation for balanced parentheses
- Cell probe lower bounds for succinct data structures
- Cell-probe lower bounds for succinct partial sums
- Changing base without losing space
- Compressed representations of permutations, and applications
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Efficient representation of perm groups
- Finding level-ancestors in trees
- Fully-functional succinct trees
- Introduction to algorithms.
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Min-wise independent permutations
- On the number of permutations admitting an \(m\)th root
- Optimal lower bounds for rank and select indexes
- Rank/select operations on large alphabets
- Representing trees of higher degree
- Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
- Succinct Ordinal Trees Based on Tree Covering
- Succinct ordinal trees with level-ancestor queries
- Succinct representation of balanced parentheses and static trees
- The cell probe complexity of succinct data structures
Cited in
(37)- On compressing permutations and adaptive sorting
- GraCT: a grammar-based compressed index for trajectory data
- Fast compressed self-indexes with deterministic linear-time construction
- Succinct representation of labeled trees
- Adjacency labeling schemes and induced-universal graphs
- Efficient fully-compressed sequence representations
- Path queries on functions
- Distance-based index structures for fast similarity search
- Notice of Removal: A Novel Representation for Permutations
- Coding for locality in reconstructing permutations
- Extra space during initialization of succinct data structures and dynamical initializable arrays
- Compact representations of spatial hierarchical structures with support for topological queries
- From time to space: fast algorithms that yield small and fast data structures
- An audit tool for genome rearrangement algorithms
- Representation of ordered trees with a given degree distribution
- Parallel construction of succinct trees
- Sampling lower bounds: Boolean average-case and permutations
- A permutations representation that knows what ``Eulerian means
- Succinct encodings for families of interval graphs
- Lempel Ziv computation in small space (LZ-CISS)
- Minimal expansions in redundant number systems and shortest paths in graphs
- Raising permutations to powers in place
- Grammar-compressed indexes with logarithmic search time
- Automata, Languages and Programming
- Compressed representations of permutations, and applications
- The function-inversion problem: barriers and opportunities
- A space-optimal grammar compression
- On the succinct representation of unlabeled permutations
- Indexing graph search trees and applications
- Simple and efficient fully-functional succinct trees
- Succinct data structure for dynamic trees with faster queries
- Succinct representation for (non)deterministic finite automata
- Path queries on functions
- A self-index on block trees
- Space-efficient algorithms for computing minimal/shortest unique substrings
- Constant time and space updates for the sigma-tau problem
- scientific article; zbMATH DE number 2038722 (Why is no real title available?)
This page was built for publication: Succinct representations of permutations and functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441860)
