Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

DOI10.4230/LIPIcs.MFCS.2020.28OpenAlexW3082278786MaRDI QIDQ5089193

Santhoshini Velusamy, Palash Dey

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12696/pdf/LIPIcs-MFCS-2020-28.pdf/

zbMATH Keywords

error-correcting codesset membershipadaptive data structuresbit-probe modelfully-explicit data structures

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two new schemes in the bitprobe model
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• Low Redundancy in Static Dictionaries with Constant Query Time
• A Survey of Data Structures in the Bitprobe Model
• Improved Explicit Data Structures in the Bitprobe Model
• Are Bitvectors Optimal?
• On a class of error correcting binary group codes
• Data Structures for Storing Small Sets in the Bitprobe Model
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Membership in Constant Time and Almost-Minimum Space
• Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements
• Set membership with a few bit probes
• Space/time trade-offs in hash coding with allowable errors

This page was built for publication: Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes