7 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…
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…