Integer Representation and Counting in the Bit Probe Model

DOI10.1007/978-3-540-77120-3_3MaRDI QIDQ5387741zbMATH OpenOpenAlexFDO

Authors M. Ziaur Rahman, J. Ian Munro

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_3

zbMATH Keywords

bit probe modeldata structureGray codelower bound

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Integer representation and counting in the bit probe model
• Integer representations towards efficient counting in the bit probe model
• Integer representations towards efficient counting in the bit probe model
• A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model
• Bit-probe lower bounds for succinct data structures

Cites work

• Are Bitvectors Optimal?
• Automata, Languages and Programming
• Dynamic word problems
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• Intersection Theorems for Systems of Sets
• Lower bounds on the size of selection and rank indexes
• Should Tables Be Sorted?

Cited in

(7)

• The counting hierarchy in binary notation
• Integer representations towards efficient counting in the bit probe model
• In-place binary counters
• Integer representations towards efficient counting in the bit probe model
• A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model
• Data structures for distributed counting
• Integer representation and counting in the bit probe model

This page was built for publication: Integer Representation and Counting in the Bit Probe Model

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