Adaptive Quotient Filters
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. Adaptive filters...
IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
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 is especially...
File System Aging
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 decisions that...
Estimating city-level travel patterns using street imagery: a case study of using Google Street View in Britain
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 features. Here we...
Bloom Filters, Adaptivity, and the Dictionary Problem
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. An AMQ...
Optimal Ball Recycling
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 as follows:...
A Fast x86 Implementation of Select
Rank and select are fundamental operations in succinct data structures, that is, data structures whose space consumption approaches the information-theoretic optimal. The performance of these...
Games Without Frontiers: Investigating Video Games as a Covert Channel
The Internet has become a critical communication infrastructure for citizens to organize protests and express dissatisfaction with their governments. This fact has not gone unnoticed, with...
The Online Event-Detection Problem
Given a stream $S = (s_1, s_2, ..., s_N)$, a $\phi$-heavy hitter is an item $s_i$ that occurs at least $\phi N$ times in $S$. The problem of finding heavy-hitters has been extensively studied in...
Don't Thrash: How to Cache Your Hash on Flash
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 found wide...
Tracking Network Events with Write Optimized Data Structures: The Design and Implementation of TWIAD: The Write-Optimized IP Address Database
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 network events such...
New Approaches to Website Fingerprinting Defenses
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 that all proposed...