Cover Image

Fingerprint Filters Are Optimal

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kuszmaul, William, Liang, Jingxun, Zhou, Renfei
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

Optimal Static Fully Indexable Dictionaries
by: Liang, Jingxun, et al.
Published: (2025)

Static Retrieval Revisited: To Optimality and Beyond
by: Hu, Yang, et al.
Published: (2025)

Optimal Non-Oblivious Open Addressing
by: Bender, Michael A., et al.
Published: (2025)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
by: Kuszmaul, William, et al.
Published: (2024)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
by: Kuszmaul, William
Published: (2025)

Tight Analyses of Ordered and Unordered Linear Probing
by: Braverman, Mark, et al.
Published: (2025)

Scheduling Jobs with Work-Inefficient Parallel Solutions
by: Kuszmaul, William, et al.
Published: (2024)

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
by: Kuszmaul, William, et al.
Published: (2021)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)

Efficient $d$-ary Cuckoo Hashing at High Load Factors by Bubbling Up
by: Kuszmaul, William, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

A Nearly Quadratic Improvement for Memory Reallocation
by: Farach-Colton, Martin, et al.
Published: (2024)

History-Independent Load Balancing
by: Bender, Michael A., et al.
Published: (2026)

Layered List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Grafite: Taming Adversarial Queries with Optimal Range Filters
by: Costa, Marco, et al.
Published: (2023)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
by: Ene, Alina, et al.
Published: (2025)

Adaptive Quotient Filters
by: Wen, Richard, et al.
Published: (2024)

Strengths and Limitations of Greedy in Cup Games
by: Jasińska, Kalina, et al.
Published: (2026)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Optimal bounds on a tree inference algorithm
by: Gardiner, Jack, et al.
Published: (2024)

Optimizing Quotient Filters using Graveyard Hashing
by: Quaye, Isabelle, et al.
Published: (2025)

A Tour of Locality Sensitive Filtering on the Sphere
by: Becchetti, Luca, et al.
Published: (2026)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Extending the Applicability of Bloom Filters by Relaxing their Parameter Constraints
by: Walther, Paul, et al.
Published: (2025)

UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search
by: Liang, Anqi, et al.
Published: (2024)

Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
by: Karathanasis, Konstantinos, et al.
Published: (2025)

Fast Construction of Partitioned Learned Bloom Filter with Theoretical Guarantees
by: Sato, Atsuki, et al.
Published: (2024)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Time To Replace Your Filter: How Maplets Simplify System Design
by: Bender, Michael A., et al.
Published: (2025)

How to Train Your Filter: Should You Learn, Stack or Adapt?
by: Sabale, Diandre Miguel, et al.
Published: (2026)

Optimal antimatroid sorting
by: Berendsohn, Benjamin Aram
Published: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Technical Report: Modeling Average False Positive Rates of Recycling Bloom Filters
by: Dozier, Kahlil, et al.
Published: (2024)