Membership in Constant Time and Almost-Minimum Space

DOI10.1137/S0097539795294165zbMath0928.68032OpenAlexW2047619746MaRDI QIDQ4268811

J. Ian Munro, Andrej Brodnik

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795294165

zbMATH Keywords

information retrievaldata structureslower bounddictionary problemsearch strategyminimum spaceefficient algorithms hashing

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items (22)

The cell probe complexity of succinct data structures ⋮ Tables should be sorted (on random access machines) ⋮ Space-efficient vertex separators for treewidth ⋮ 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 ⋮ On the succinct representation of equivalence classes ⋮ Succinct encoding of arbitrary graphs ⋮ A uniform paradigm to succinctly encode various families of trees ⋮ Fast Evaluation of Union-Intersection Expressions ⋮ Faster Practical Block Compression for Rank/Select Dictionaries ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Determining membership with 2 simultaneous queries ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ The simultaneous conjugacy problem in the symmetric group ⋮ Cuckoo hashing: Further analysis ⋮ Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes ⋮ An Optimal Bloom Filter Replacement Based on Matrix Solving ⋮ Orthogonal Range Searching for Text Indexing ⋮ A Survey of Data Structures in the Bitprobe Model

This page was built for publication: Membership in Constant Time and Almost-Minimum Space