6 papers
The Case for External Graph Sketching
Michael A. Bender, MartÃn Farach-Colton, Riko Jacob +3
Algorithms in the data stream model use space to compute some property of an input of size , and many of these algorithms are implemented and used in practice. H…
Exploring the Landscape of Distributed Graph Sketching
David Tench, Evan T. West, Kenny Zhang +6
Recent work has initiated the study of dense graph processing using graph sketching methods, which drastically reduce space costs by lossily compressing information about the input…
A Nearly Quadratic Improvement for Memory Reallocation
Martin Farach-Colton, William Kuszmaul, Nathan Sheffield +1
In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the…
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…
Nearly Optimal List Labeling
Michael A. Bender, Alex Conway, MartÃn Farach-Colton +4
The list-labeling problem captures the basic task of storing a dynamically changing set of up to elements in sorted order in an array of size . The goal is to…
Layered List Labeling
Michael A. Bender, Alex Conway, Martin Farach-Colton +2
The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and…