10 papers · 1 filter
Incremental Strongly Connected Components with Predictions
Ronald Deng, Samuel McCauley, Aidin Niaparast +5
Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework…
Space-Efficient Text Indexing with Mismatches using Function Inversion
Jackson Bibbens, Levi Borevitz, Samuel McCauley
A classic data structure problem is to preprocess a string T of length so that, given a query , we can quickly find all substrings of T with Hamming distance at most fro…
Incremental Approximate Single-Source Shortest Paths with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +2
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing inte…
SPIDER: Improved Succinct Rank and Select Performance
Matthew D. Laws, Jocelyn Bliven, Kit Conklin +3
Rank and select data structures seek to preprocess a bit vector to quickly answer two kinds of queries: rank(i) gives the number of 1 bits in slots 0 through i, and select(j) gives…
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…
Support Optimality and Adaptive Cuckoo Filters
Tsvi Kopelowitz, Samuel McCauley, Ely Porat
Filters (such as Bloom Filters) are data structures that speed up network routing and measurement operations by storing a compressed representation of a set. Filters are space effi…