Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)

DOI10.1007/978-3-540-70575-8_32MaRDI QIDQ3521934zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dietzfelbinger, Rasmus Pagh

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_32

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Recommendations

• Succinct data structures for flexible text retrieval systems
• A space lower bound for dynamic approximate membership data structures
• Algorithms and Computation
• Succinct data structures for searchable partial sums with optimal worst-case performance
• scientific article; zbMATH DE number 1982202
• scientific article; zbMATH DE number 1979483
• Hashing and indexing: succinct data structures and smoothed analysis

Cited in

(27)

• Efficient and error-correcting data structures for membership and polynomial evaluation
• Sharp load thresholds for cuckoo hashing
• An Optimal Bloom Filter Replacement Based on Matrix Solving
• Storing a Compressed Function with Constant Time Access
• scientific article; zbMATH DE number 4104389 (Why is no real title available?)
• Various improvements to text fingerprinting
• scientific article; zbMATH DE number 1982202 (Why is no real title available?)
• Dense peelable random uniform hypergraphs
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• Constant-time retrieval with O( m) extra bits
• Binary fuse filters: fast and smaller than xor filters
• Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations
• Bloom maps
• Conjunctive filter: breaking the entropy barrier
• Approximate range emptiness in constant time and optimal space
• Exact and approximate membership testers
• A space lower bound for dynamic approximate membership data structures
• Compressed static functions with applications
• Tight tradeoffs in searchable symmetric encryption
• Tight bounds for sliding Bloom filters
• Xor Filters
• Daisy Bloom filters
• Dynamic filter and retrieval with one access to modifiable memory
• Tiny pointers
• Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures
• Ribbon: fast succinct static retrieval and approximate membership
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions

This page was built for publication: Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)

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