Compressed data structures: Dictionaries and data-aware measures
From MaRDI portal
Publication:2465063
DOI10.1016/j.tcs.2007.07.042zbMath1144.68017OpenAlexW2100970422MaRDI QIDQ2465063
Wing-Kai Hon, Jeffrey Scott Vitter, Rahul Shah, Ankur Gupta
Publication date: 19 December 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.042
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (9)
Range selection and predecessor queries in data aware space and time ⋮ On the succinct representation of equivalence classes ⋮ Entropy-bounded representation of point grids ⋮ \(E=I+T\): the internal extent formula for compacted tries ⋮ Optimal indexes for sparse bit vectors ⋮ Efficient dynamic range minimum query ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Efficient and compact representations of some non-canonical prefix-free codes ⋮ Adaptive succinctness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New trie data structures which support very fast search operations
- Surpassing the information theoretic bound with fusion trees
- Optimal bounds for the predecessor problem
- Time-space trade-offs for predecessor search
- Tight(er) worst-case bounds on dynamic searching and priority queues
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Squeezing succinct data structures into entropy bounds
- Universal codeword sets and representations of the integers
- Design and implementation of an efficient priority queue
- Membership in Constant Time and Almost-Minimum Space
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
This page was built for publication: Compressed data structures: Dictionaries and data-aware measures
