Compressed data structures: Dictionaries and data-aware measures

DOI10.1016/J.TCS.2007.07.042MaRDI QIDQ2465063zbMATH OpenOpenAlexFDO

Authors Ankur Gupta, Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter

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

zbMATH Keywords

rankdictionary problemcompressedselectpredecessorBSGAPgap encoding

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Compressed Dictionaries: Space Measures, Data Sets, and Experiments
• Compressed string dictionaries via data-aware subtrie compaction
• A general framework for dynamic succinct and compressed data structures
• Compressed Data Separation With Redundant Dictionaries
• scientific article; zbMATH DE number 2182423
• scientific article; zbMATH DE number 2087558
• Hierarchical dictionary model and dictionary management policies for data compression
• Optimal-Time Dictionary-Compressed Indexes
• Compressed Data Structures for Dynamic Sequences

Cites work

• scientific article; zbMATH DE number 3755865 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 756768 (Why is no real title available?)
• Compact representations of ordered sets
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Design and implementation of an efficient priority queue
• Dictionaries using variable-length keys and data, with applications
• Membership in Constant Time and Almost-Minimum Space
• New trie data structures which support very fast search operations
• Optimal bounds for the predecessor problem
• Squeezing succinct data structures into entropy bounds
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Surpassing the information theoretic bound with fusion trees
• Tight(er) worst-case bounds on dynamic searching and priority queues
• Time-space trade-offs for predecessor search
• Universal codeword sets and representations of the integers

Cited in

(18)

• Optimal indexes for sparse bit vectors
• Disk compression of \(k\)-mer sets
• Adaptive succinctness
• Adaptive succinctness
• Efficient and compact representations of some non-canonical prefix-free codes
• Compressed Data Structures for Dynamic Sequences
• On the succinct representation of equivalence classes
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• A new compression method of double array for compact dictionaries
• A Learned Approach to Design Compressed Rank/Select Data Structures
• BOUNDED SIZE DICTIONARY COMPRESSION: RELAXING THE LRU DELETION HEURISTIC
• On compact representations of all-pairs-shortest-path-distance matrices
• Preface -- Compact data structures
• Range selection and predecessor queries in data aware space and time
• Efficient dynamic range minimum query
• Compressed Dictionaries: Space Measures, Data Sets, and Experiments
• Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
• Entropy-bounded representation of point grids

This page was built for publication: Compressed data structures: Dictionaries and data-aware measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465063)