Optimizing Quotient Filters using Graveyard Hashing
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916635084849152 |
|---|---|
| author | Quaye, Isabelle Taylor, Temi |
| author_facet | Quaye, Isabelle Taylor, Temi |
| contents | We aim to improve the performance of the Quotient Filter at high load factors. Our Graveyard Filter is a variation of the Quotient Filter which incorporates Graveyard Hashing, a technique that uses tombstones to counteract the effects of primary clustering. We summarize our implementation of the graveyard filter and detail approaches to redistributing tombstones. Evaluating these variations under conditions similar to the original quotient filter paper, we found the performance of the graveyard filter to be competitive for insertion and query operations, with certain redistribution schemes showing stronger performance at high load factors. We discuss potential further improvements, such as using the current load factor to determine the employed redistribution approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimizing Quotient Filters using Graveyard Hashing Quaye, Isabelle Taylor, Temi Data Structures and Algorithms We aim to improve the performance of the Quotient Filter at high load factors. Our Graveyard Filter is a variation of the Quotient Filter which incorporates Graveyard Hashing, a technique that uses tombstones to counteract the effects of primary clustering. We summarize our implementation of the graveyard filter and detail approaches to redistributing tombstones. Evaluating these variations under conditions similar to the original quotient filter paper, we found the performance of the graveyard filter to be competitive for insertion and query operations, with certain redistribution schemes showing stronger performance at high load factors. We discuss potential further improvements, such as using the current load factor to determine the employed redistribution approach. |
| title | Optimizing Quotient Filters using Graveyard Hashing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.20725 |