4 papers
Telescoping Filter: A Practical Adaptive Filter
David J. Lee, Samuel McCauley, Shikha Singh +1
Filters are fast, small and approximate set membership data structures. They are often used to filter out expensive accesses to a remote set S for negative queries (that is, a quer…
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 stu…
Efficient Rational Proofs with Strong Utility-Gap Guarantees
Jing Chen, Samuel McCauley, Shikha Singh
As modern computing moves towards smaller devices and powerful cloud platforms, more and more computation is being delegated to powerful service providers. Interactive proofs are a…
Run Generation Revisited: What Goes Up May or May Not Come Down
Michael A. Bender, Samuel McCauley, Andrew McGregor +2
In this paper, we revisit the classic problem of run generation. Run generation is the first phase of external-memory sorting, where the objective is to scan through the data, reor…