250 citations · 1.1k across the 76 of their papers we have counts for
45 papers · 1 filter
SALSA: Self-Adjusting Lean Streaming Analytics
Ran Ben Basat, Gil Einziger, Michael Mitzenmacher +1
Counters are the fundamental building block of many data sketching schemes, which hash items to a small number of counters and account for collisions to provide good approximations…
Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
Michael Mitzenmacher, Saeed Seddighin
In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (\textsf{LIS}) problem, and the complementary distance to monoto…
Erdös-Szekeres Partitioning Problem
Michael Mitzenmacher, Saeed Seddighin
In this note, we present a substantial improvement on the computational complexity of the Erdös-Szekeres partitioning problem and review recent works on dynamic \textsf{LIS}.
Algorithms with Predictions
Michael Mitzenmacher, Sergei Vassilvitskii
We introduce algorithms that use predictions from machine learning applied to the input to circumvent worst-case analysis. We aim for algorithms that have near optimal performance…
Partitioned Learned Bloom Filter
Kapil Vaidya, Eric Knorr, Tim Kraska +1
Bloom filters are space-efficient probabilistic data structures that are used to test whether an element is a member of a set, and may return false positives. Recently, variations…
Faster and More Accurate Measurement through Additive-Error Counters
Ran Ben Basat, Gil Einziger, Michael Mitzenmacher +1
Counters are a fundamental building block for networking applications such as load balancing, traffic engineering, and intrusion detection, which require estimating flow sizes and…