4 citations · 7 across the 6 of their papers we have counts for
10 papers
Locally Uniform Hashing
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen +2
Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical re…
Daisy Bloom Filters
Ioana O. Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh
A filter is a widely used data structure for storing an approximation of a given set of elements from some universe (a countable set).It represents a superset $S'\supseteq…
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-…
On the cost of essentially fair clusterings
Ioana O. Bercea, Martin Groß, Samir Khuller +4
Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this proc…
Improved Bounds for the Traveling Salesman Problem with Neighborhoods on Uniform Disks
Ioana O. Bercea
Given a set of disks of radius in the Euclidean plane, the Traveling Salesman Problem With Neighborhoods (TSPN) on uniform disks asks for the shortest tour that visits all…
Minimizing Uncertainty through Sensor Placement with Angle Constraints
Ioana O. Bercea, Volkan Isler, Samir Khuller
We study the problem of sensor placement in environments in which localization is a necessity, such as ad-hoc wireless sensor networks that allow the placement of a few anchors tha…
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Ioana O. Bercea, Navin Goyal, David G. Harris +1
Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Unlike the w…