Cover Image

A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agarwala, Aryan, Even, Guy
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms E.1; E.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

FlipHash: A Constant-Time Consistent Range-Hashing Algorithm
by: Masson, Charles, et al.
Published: (2024)

DynamicLogLog: Faster, Smaller, and More Accurate Cardinality Estimation
by: Bushnell, Brian
Published: (2026)

Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores
by: Garg, Ishant
Published: (2026)

MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing
by: Hermann, Stefan
Published: (2025)

Sampling Space-Saving Set Sketches
by: Lee, Homin K., et al.
Published: (2024)

Faster Linear-Space Data Structures for Path Frequency Queries
by: Rata, Ovidiu
Published: (2026)

On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited
by: Krawczyk, Tomasz
Published: (2024)

New Entropy Measures for Tries with Applications to the XBWT
by: Carfagna, Lorenzo, et al.
Published: (2025)

A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
by: Lecroq, Thierry
Published: (2024)

Optimal Preprocessing for Answering On-Line Product Queries
by: Alon, Noga, et al.
Published: (2024)

Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
by: Brodal, Gerth Stølting
Published: (2024)

Highway Preferential Attachment Models for Geographic Routing
by: Gila, Ofek, et al.
Published: (2024)

Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
by: Gila, Ofek, et al.
Published: (2023)

Cache-Oblivious Representation of B-Tree Structures
by: Ondráček, Lukáš, et al.
Published: (2022)

Fast Geographic Routing in Fixed-Growth Graphs
by: Gila, Ofek, et al.
Published: (2025)

A Computational Proof of the Highest-Scoring Boggle Board
by: Vanderkam, Dan
Published: (2025)

Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"
by: Krawczyk, Tomasz
Published: (2024)

Cheesemap: A High-Performance Point-Indexing Data Structure for Neighbor Search in LiDAR Data
by: Laso, Ruben, et al.
Published: (2025)

Evaluating Learned Indexes in LSM-tree Systems: Benchmarks,Insights and Design Choices
by: Liu, Junfeng, et al.
Published: (2025)

An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane
by: Sitters, René
Published: (2025)

The Chonkers Algorithm: Content-Defined Chunking with Provable Strict Guarantees on Size and Locality
by: Berger, Benjamin
Published: (2025)

A (Weakly) Polynomial Algorithm for AIVF Coding
by: Dolatabadi, Reza Hosseini, et al.
Published: (2024)

Rahmani Sort: A Novel Variant of Insertion Sort Algorithm with O(nlogn) Complexity
by: Rahmani, Mohammad Khalid Imam
Published: (2024)

BlockFIFO & MultiFIFO: Scalable Relaxed Queues
by: Koch, Stefan, et al.
Published: (2025)

On generating $k$-factorable graphic sequences with connected (resp.no connected) $k$-factors
by: Mukhopadhyay, Asish, et al.
Published: (2024)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
by: Bell, Tolson, et al.
Published: (2024)

Better Algorithms for Constructing Minimum Cost Markov Chains and AIFV Codes
by: Dolatabadi, Reza Hosseini, et al.
Published: (2024)

Dynamic Indexing Through Learned Indices with Worst-case Guarantees
by: Gæde, Emil Toftegaard, et al.
Published: (2025)

Sublime: Sublinear Error & Space for Unbounded Skewed Streams
by: Eslami, Navid, et al.
Published: (2026)

The Merkle Mountain Belt
by: Cevallos, Alfonso, et al.
Published: (2025)

An Efficient Algorithm for Unbalanced 1D Transportation
by: Gouvine, Gabriel
Published: (2023)

A Knowledge Compilation Map for Quantum Information
by: Vinkhuijzen, Lieuwe, et al.
Published: (2024)

static_maps: consteval std::map and std::unordered_map Implementations in C++23
by: Myhal, Isaac D., et al.
Published: (2026)

Enabling Skip Graphs to Process K-Dimensional Range Queries in a Mobile Sensor Network
by: Brault, Gregory J., et al.
Published: (2024)

Techniques for Authenticating Quantile Digests
by: Scala, Alessandro
Published: (2024)

An 8- and 12-bit block AES cipher
by: Breuer, Peter T.
Published: (2025)

Adversarial Robustness on Insertion-Deletion Streams
by: Gribelyuk, Elena, et al.
Published: (2026)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)

An Efficient Algorithm for Permutation Iteration Using a Singly Linked List
by: Baruchel, Thomas
Published: (2025)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)