52 citations · 106 across the 21 of their papers we have counts for
33 papers
Prefix Filter: Practically and Theoretically Better Than Bloom
Tomer Even, Guy Even, Adam Morrison
Many applications of approximate membership query data structures, or filters, require only an incremental filter that supports insertions but not deletions. However, the design sp…
A Dynamic Space-Efficient Filter with Constant Time Operations
Ioana Oriana Bercea, Guy Even
A dynamic dictionary is a data structure that maintains sets of cardinality at most from a given universe and supports insertions, deletions, and membership queries. A filter a…
A Space-Efficient Dynamic Dictionary for Multisets with Constant Time Operations
Ioana Oriana Bercea, Guy Even
We consider the dynamic dictionary problem for multisets. Given an upper bound on the total cardinality of the multiset (i.e., including multiplicities) at any point in time, t…
Upper Tail Analysis of Bucket Sort and Random Tries
Ioana O. Bercea, Guy Even
Bucket Sort is known to run in expected linear time when the input keys are distributed independently and uniformly at random in the interval . The analysis holds even when…
Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses
Ioana O. Bercea, Guy Even
A fully-dynamic dictionary is a data structure for maintaining sets that supports insertions, deletions and membership queries. A filter approximates membership queries with a one-…
Optimal Distributed Covering Algorithms
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank . This problem is equivalent to the Minimum…