Low Redundancy in Static Dictionaries with Constant Query Time
From MaRDI portal
Publication:2784457
DOI10.1137/S0097539700369909zbMath0994.68050OpenAlexW1986970296MaRDI QIDQ2784457
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700369909
Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information storage and retrieval of data (68P20)
Related Items
Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ The cell probe complexity of succinct data structures ⋮ GLOUDS: representing tree-like graphs ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Fast and simple compact hashing via bucketing ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Implicit \(B\)-trees: A new data structure for the dictionary problem ⋮ Entropy-bounded representation of point grids ⋮ Succinct encoding of arbitrary graphs ⋮ Ultra-succinct representation of ordered trees with applications ⋮ A uniform paradigm to succinctly encode various families of trees ⋮ m-Bonsai: A Practical Compact Dynamic Trie ⋮ Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ Determining membership with 2 simultaneous queries ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Linear-time compression of 2-manifold polygon meshes into information-theoretically optimal number of bits ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Dispersing hash functions ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes ⋮ A Survey of Data Structures in the Bitprobe Model
