6 citations · 9 across the 4 of their papers we have counts for
6 papers
DartMinHash: Fast Sketching for Weighted Sets
Tobias Christiani
Weighted minwise hashing is a standard dimensionality reduction technique with applications to similarity search and large-scale kernel machines. We introduce a simple algorithm th…
PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
Martin Aumüller, Tobias Christiani, Rasmus Pagh +1
We present PUFFINN, a parameterless LSH-based index for solving the -nearest neighbor problem with probabilistic guarantees. By parameterless we mean that the user is only requi…
Algorithms for Similarity Search and Pseudorandomness
Tobias Christiani
We study the problem of approximate near neighbor (ANN) search and show the following results: - An improved framework for solving the ANN problem using locality-sensitive hashing,…
Confirmation Sampling for Exact Nearest Neighbor Search
Tobias Christiani, Rasmus Pagh, Mikkel Thorup
Locality-sensitive hashing (LSH), introduced by Indyk and Motwani in STOC '98, has been an extremely influential framework for nearest neighbor search in high-dimensional data sets…
Optimal Boolean Locality-Sensitive Hashing
Tobias Christiani
For the distribution over Boolean functions that minimizes the expression \begin{equation*} ρ_{α, β} = \frac{\lo…
From Independence to Expansion and Back Again
Tobias Christiani, Rasmus Pagh, Mikkel Thorup
We consider the following fundamental problems: (1) Constructing -independent hash functions with a space-time tradeoff close to Siegel's lower bound. (2) Constructing represent…