Rob Johnson 0001

SODA Conference 2020 Conference Paper

Flushing Without Cascades

• Michael A. Bender
• Rathish Das
• Martín Farach-Colton
• Rob Johnson 0001
• William Kuszmaul

SODA Conference 2019 Conference Paper

Optimal Ball Recycling

• Michael A. Bender
• Jake Christensen
• Alex Conway 0001
• Martín Farach-Colton
• Rob Johnson 0001
• Meng-Tsung Tsai

Balls-and-bins games have been a successful tool for modeling load balancing problems. In this paper, we study a new scenario, which we call the ball-recycling game, defined as follows: Throw m balls into n bins i. i. d. according to a given probability distribution p. Then, at each time step, pick a non-empty bin and recycle its balls: take the balls from the selected bin and re-throw them according to p. This balls-and-bins game closely models memory-access heuristics in databases. The goal is to have a bin-picking method that maximizes the recycling rate, defined to be the expected number of balls recycled per step in the stationary distribution. We study two natural strategies for ball recycling: F ullest B in, which greedily picks the bin with the maximum number of balls, and R andom B all, which picks a ball at random and recycles its bin. We show that for general p, random B all is Θ(1)-optimal, whereas F ullest B in can be pessimal. However, when p = u, the uniform distribution, F ullest B in is optimal to within an additive constant.

FOCS Conference 2018 Conference Paper

Bloom Filters, Adaptivity, and the Dictionary Problem

• Michael A. Bender
• Martín Farach-Colton
• Mayank Goswami 0001
• Rob Johnson 0001
• Samuel McCauley
• Shikha Singh 0002

An approximate membership query data structure (AMQ)-such as a Bloom, quotient, or cuckoo filter-maintains a compact, probabilistic representation of a set S of keys from a universe U. It supports lookups and inserts. Some AMQs also support deletes. A query for x ∈ S returns PRESENT. A query for x ∉ S returns PRESENT with a tunable false-positive probability ε, and otherwise returns ABSENT. AMQs are widely used to speed up dictionaries that are stored remotely (e. g. , on disk or across a network). The AMQ is stored locally (e. g. , in memory). The remote dictionary is only accessed when the AMQ returns PRESENT. Thus, the primary performance metric of an AMQ is how often it returns ABSENT for negative queries. Existing AMQs offer weak guarantees on the number of false positives in a sequence of queries. The false-positive probability ε holds only for a single query. It is easy for an adversary to drive an AMQ's false-positive rate towards 1 by simply repeating false positives. This paper shows what it takes to get strong guarantees on the number of false positives. We say that an AMQ is adaptive if it guarantees a false-positive probability of ε for every query, regardless of answers to previous queries. We establish upper and lower bounds for adaptive AMQs. Our lower bound shows that it is impossible to build a small adaptive AMQ, even when the AMQ is immediately told whenever a query is a false positive. On the other hand, we show that it is possible to maintain an AMQ that uses the same amount of local space as a non-adaptive AMQ (up to lower order terms), performs all queries and updates in constant time, and guarantees that each negative query to the dictionary accesses remote storage with probability ε, independent of the results of past queries. Thus, we show that adaptivity can be achieved effectively for free.

SODA Conference 2014 Conference Paper

Cache-Adaptive Algorithms

• Michael A. Bender
• Roozbeh Ebrahimi
• Jeremy T. Fineman
• Golnaz Ghasemiesfeh
• Rob Johnson 0001
• Samuel McCauley

We introduce the cache-adaptive model, which generalizes the external-memory model to apply to environments in which the amount of memory available to an algorithm can fluctuate. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. We prove that if an optimal cache-oblivious algorithm has a particular recursive structure, then it is also an optimal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naïve recursive matrix multiplication, matrix transpose, and Gaussian elimination. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have this recursive structure, we prove that it is nonetheless optimally cache-adaptive. We also establish that if a cache-oblivious algorithm is optimal on “square”” (well-behaved) memory profiles then, given resource augmentation it is optimal on all memory profiles. We give paging algorithms for the case where the cache size changes dynamically. We prove that LRU with 4-memory and 4-speed augmentation is competitive with optimal. Moreover, Belady's algorithm remains optimal even when the cache size changes. Cache-obliviousness is distinct from cache-adaptivity. We exhibit a cache-oblivious algorithm that is not cache-adaptive and a cache-adaptive algorithm for a problem having no optimal cache-oblivious solution. MSC codes cache adaptive cache oblivious external memory memory adaptive paging algorithms