• The Fuse XORier Lookup Table:...

Result: The Fuse XORier Lookup Table: Exploration, Implementation, and Revision of Probabilistic Sets and Maps

Title:
The Fuse XORier Lookup Table: Exploration, Implementation, and Revision of Probabilistic Sets and Maps
Authors:
Breyer, Eric, Liu, Alan
Publication Year:
2023
Collection:
Computer Science
Subject Terms:
Computer Science - Data Structures and Algorithms
Document Type:
Report Working Paper
Access URL:
http://arxiv.org/abs/2312.13541
Accession Number:
edsarx.2312.13541
Database:
arXiv

Further Information

This paper presents an exploration, implementations, and revisions of probabilistic sets and maps, specifically focusing on Bloomier filters and related data structures. The paper introduces the Fuse XORier Lookup Table (FXLT), an enhanced version of the Bloomier Filter incorporating spatial coupling, linear construction, and optimizations. The authors provide implementations in C and Python, comparing the FXLT's performance with other data structures like bloom filters, XOR filters, binary fuse filters, hash tables, and red-black trees. The FXLT demonstrates improvements in both space and time efficiency over traditional Bloomier Filters and appears competitive with hash tables for large datasets.