Publications (19)
Adaptive Quotient Filters
Richard Wen, Hunter McCoy, David Tench +6
Adaptive filters, such as telescoping and adaptive cuckoo filters, update their representation upon detecting a false positive to avoid repeating the same error in the future. Adap…
A Fast x86 Implementation of Select
Prashant Pandey, Michael A. Bender, Rob Johnson
Rank and select are fundamental operations in succinct data structures, that is, data structures whose space consumption approaches the information-theoretic optimal. The performan…
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
Prashant Pandey, Michael A. Bender, Alex Conway +4
Modern hash table designs strive to minimize space while maximizing speed. The most important factor in speed is the number of cache lines accessed during updates and queries. This…
How Best to Handle a Dicey Situation
Rishab Nithyanand, Jonathan Toohill, Rob Johnson
We introduce the {Destructive Object Handling} (DOH) problem, which models aspects of many real-world allocation problems, such as shipping explosive munitions, scheduling processe…
Games Without Frontiers: Investigating Video Games as a Covert Channel
Bridger Hahn, Rishab Nithyanand, Phillipa Gill +1
The Internet has become a critical communication infrastructure for citizens to organize protests and express dissatisfaction with their governments. This fact has not gone unnotic…
Don't Thrash: How to Cache Your Hash on Flash
Michael A. Bender, Martin Farach-Colton, Rob Johnson +7
This paper presents new alternatives to the well-known Bloom filter data structure. The Bloom filter, a compact data structure supporting set insertion and membership queries, has…
Bloom Filters, Adaptivity, and the Dictionary Problem
Michael A. Bender, Martin Farach-Colton, Mayank Goswami +3
The Bloom filter---or, more generally, an approximate membership query data structure (AMQ)---maintains a compact, probabilistic representation of a set S of keys from a universe U…
Bayesian profile regression for clustering analysis involving a longitudinal response and explanatory variables
Anaïs Rouanet, Rob Johnson, Magdalena E Strauss +4
The identification of sets of co-regulated genes that share a common function is a key question of modern genomics. Bayesian profile regression is a semi-supervised mixture modelli…
Estimating city-level travel patterns using street imagery: a case study of using Google Street View in Britain
Rahul Goel, Leandro M. T. Garcia, Anna Goodman +6
Street imagery is a promising big data source providing current and historical images in more than 100 countries. Previous studies used this data to audit built environment feature…
Fast Concurrent Primitives Despite Contention
Michael A. Bender, Guy E. Blelloch, Martin Farach-Colton +4
We study the problem of constructing concurrent objects in a setting where processes run in parallel and interact through a shared memory that is subject to write contention. O…
New Approaches to Website Fingerprinting Defenses
Xiang Cai, Rishab Nithyanand, Rob Johnson
Website fingerprinting attacks enable an adversary to infer which website a victim is visiting, even if the victim uses an encrypting proxy, such as Tor. Previous work has shown th…
Time To Replace Your Filter: How Maplets Simplify System Design
Michael A. Bender, Alex Conway, MartÃn Farach-Colton +2
Filters such as Bloom, quotient, and cuckoo filters are fundamental building blocks providing space-efficient approximate set membership testing. However, many applications need to…
File System Aging
Alex Conway, Ainesh Bakshi, Arghya Bhattacharya +11
File systems must allocate space for files without knowing what will be added or removed in the future. Over the life of a file system, this may cause suboptimal file placement dec…
The Online Event-Detection Problem
Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton +5
Given a stream , a -heavy hitter is an item that occurs at least times in . The problem of finding heavy-hitters has been extensively s…
Tracking Network Events with Write Optimized Data Structures: The Design and Implementation of TWIAD: The Write-Optimized IP Address Database
Nolan Donoghue, Bridger Hahn, Helen Xu +3
Access to network traffic records is an integral part of recognizing and addressing network security breaches. Even with the increasing sophistication of network attacks, basic net…
Optimal Ball Recycling
Michael A. Bender, Jake Christensen, Alex Conway +3
Balls-and-bins games have been a wildly successful tool for modeling load balancing problems. In this paper, we study a new scenario, which we call the ball recycling game, defined…
Efficiently Constructing Sparse Navigable Graphs
Alex Conway, Laxman Dhulipala, Martin Farach-Colton +6
Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to…
A guide to Value of Information methods for prioritising research in health impact modelling
Rob Johnson, James Woodcock, Audrey de Nazelle +4
Health impact simulation models are used to predict how a proposed intervention or scenario will affect public health outcomes, based on available data and knowledge of the process…
Quantifying efficiency gains of innovative designs of two-arm vaccine trials for COVID-19 using an epidemic simulation model
Rob Johnson, Chris Jackson, Anne Presanis +2
Clinical trials of a vaccine during an epidemic face particular challenges, such as the pressure to identify an effective vaccine quickly to control the epidemic, and the effect th…