Membership in Constant Time and Almost-Minimum Space

DOI10.1137/S0097539795294165MaRDI QIDQ4268811zbMATH OpenOpenAlexFDO

Authors Andrej Brodnik, J. Ian Munro

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

data structuresdictionary problemefficient algorithms hashinginformation retrievallower boundminimum spacesearch strategy

Mathematics Subject Classification ID

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

Recommendations

• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Are Bitvectors Optimal?
• Set membership with a few bit probes
• Are bitvectors optimal?

Cited in

(26)

• Cuckoo hashing: Further analysis
• Threshold data structures and coding theory
• Space-efficient vertex separators for treewidth
• Fast and simple compact hashing via bucketing
• Determining membership with 2 simultaneous queries
• The cell probe complexity of succinct data structures
• On the succinct representation of equivalence classes
• A uniform paradigm to succinctly encode various families of trees
• Compressed data structures: Dictionaries and data-aware measures
• Orthogonal range searching for text indexing
• A Survey of Data Structures in the Bitprobe Model
• An Optimal Bloom Filter Replacement Based on Matrix Solving
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct encoding of arbitrary graphs
• The simultaneous conjugacy problem in the symmetric group
• Tables should be sorted (on random access machines)
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• Faster practical block compression for rank/select dictionaries
• Fast Evaluation of Union-Intersection Expressions
• Exact and approximate membership testers
• A quick tour on suffix arrays and compressed suffix arrays
• Implicit \(B\)-trees: A new data structure for the dictionary problem
• On regularity lemma and barriers in streaming and dynamic matching
• Tables
• Succinct data structures for searchable partial sums with optimal worst-case performance

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

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