2 citations · 5 across the 13 of their papers we have counts for
19 papers
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…
Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
Samuel McCauley, Benjamin Moseley, Helia Niaparast +1
In this paper, we study the fundamental problem of finding a stable matching in two-sided matching markets. In the classic variant, it is assumed that both sides of the market subm…
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…
Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
Samuel McCauley
Approximate nearest neighbor search (ANN) data structures have widespread applications in machine learning, computational biology, and text processing. The goal of ANN is to prepro…
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…
Root-to-Leaf Scheduling in Write-Optimized Trees
Christopher Chung, William Jannen, Samuel McCauley +1
Write-optimized dictionaries are a class of cache-efficient data structures that buffer updates and apply them in batches to optimize the amortized cache misses per update. For exa…
Incremental Topological Ordering and Cycle Detection with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +1
This paper leverages the framework of algorithms-with-predictions to design data structures for two fundamental dynamic graph problems: incremental topological ordering and cycle d…
Online List Labeling with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +1
A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating prediction…
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…
Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
Samuel McCauley
Edit distance similarity search, also called approximate pattern matching, is a fundamental problem with widespread database applications. The goal of the problem is to preprocess…
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…
Adaptive MapReduce Similarity Joins
Samuel McCauley, Francesco Silvestri
Similarity joins are a fundamental database operation. Given data sets S and R, the goal of a similarity join is to find all points x in S and y in R with distance at most r. Recen…
Set Similarity Search for Skewed Data
Samuel McCauley, Jesper W. Mikkelsen, Rasmus Pagh
Set similarity join, as well as the corresponding indexing problem set similarity search, are fundamental primitives for managing noisy or uncertain data. For example, these primit…
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…
Non-Cooperative Rational Interactive Proofs
Jing Chen, Samuel McCauley, Shikha Singh
Interactive-proof games model the scenario where an honest party interacts with powerful but strategic provers, to elicit from them the correct answer to a computational question.…
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…
Rational Proofs with Multiple Provers
Jing Chen, Samuel McCauley, Shikha Singh
Interactive proofs (IP) model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover's claims before accepting them. IP protocols have appl…