Simple Set Sketching
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Simple Set Sketching. / Bæk Tejs Houen, Jakob; Pagh, Rasmus; Walzer, Stefan.
Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA). red. / Telikepalli Kavitha; Kurt Mehlhorn. Society for Industrial and Applied Mathematics, 2023. s. 228-241.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Simple Set Sketching
AU - Bæk Tejs Houen, Jakob
AU - Pagh, Rasmus
AU - Walzer, Stefan
PY - 2023
Y1 - 2023
N2 - Imagine handling collisions in a hash table by storing, in each cell, the bit-wise exclusive-or of the set of keys hashing there. This appears to be a terrible idea: For an keys and n buckets, where α is constant, we expect that a constant fraction of the keys will be unrecoverable due to collisions.We show that if this collision resolution strategy is repeated three times independently the situation reverses: If α is below a threshold of ≈ 0.81 then we can recover the set of all inserted keys in linear time with high probability.Even though the description of our data structure is simple, its analysis is nontrivial. Our approach can be seen as a variant of the Invertible Bloom Filter (IBF) of Eppstein and Goodrich. While IBFs involve an explicit checksum per bucket to decide whether the bucket stores a single key, we exploit the idea of quotienting, namely that some bits of the key are implicit in the location where it is stored. We let those serve as an implicit checksum. These bits are not quite enough to ensure that no errors occur and the main technical challenge is to show that decoding can recover from these errors.
AB - Imagine handling collisions in a hash table by storing, in each cell, the bit-wise exclusive-or of the set of keys hashing there. This appears to be a terrible idea: For an keys and n buckets, where α is constant, we expect that a constant fraction of the keys will be unrecoverable due to collisions.We show that if this collision resolution strategy is repeated three times independently the situation reverses: If α is below a threshold of ≈ 0.81 then we can recover the set of all inserted keys in linear time with high probability.Even though the description of our data structure is simple, its analysis is nontrivial. Our approach can be seen as a variant of the Invertible Bloom Filter (IBF) of Eppstein and Goodrich. While IBFs involve an explicit checksum per bucket to decide whether the bucket stores a single key, we exploit the idea of quotienting, namely that some bits of the key are implicit in the location where it is stored. We let those serve as an implicit checksum. These bits are not quite enough to ensure that no errors occur and the main technical challenge is to show that decoding can recover from these errors.
U2 - 10.1137/1.9781611977585.ch21
DO - 10.1137/1.9781611977585.ch21
M3 - Article in proceedings
SP - 228
EP - 241
BT - Proceedings, 2023 Symposium on Simplicity in Algorithms (SOSA)
A2 - Kavitha, Telikepalli
A2 - Mehlhorn, Kurt
PB - Society for Industrial and Applied Mathematics
T2 - 2023 Symposium on Simplicity in Algorithms (SOSA)
Y2 - 23 January 2023 through 25 January 2023
ER -
ID: 382689570