6 citations · 12 across the 9 of their papers we have counts for
12 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…
Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search
Tobias Christiani
The Indyk-Motwani Locality-Sensitive Hashing (LSH) framework (STOC 1998) is a general technique for constructing a data structure to answer approximate near neighbor queries by usi…
Scalable and robust set similarity join
Tobias Christiani, Rasmus Pagh, Johan Sivertsen
Set similarity join is a fundamental and well-studied database operator. It is usually studied in the exact setting where the goal is to compute all pairs of sets that exceed a giv…
Distance-Sensitive hashing
Martin Aumüller, Tobias Christiani, Rasmus Pagh +1
Locality-sensitive hashing (LSH) is an important tool for managing high-dimensional noisy or uncertain data, for example in connection with data cleaning (similarity join) and nois…
Set Similarity Search Beyond MinHash
Tobias Christiani, Rasmus Pagh
We consider the problem of approximate set similarity search under Braun-Blanquet similarity $B(\mathbf{x}, \mathbf{y}) = |\mathbf{x} \cap \mathbf{y}| / \max(|\mathbf{x}|, |\mathbf…
A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
Tobias Christiani
We present a framework for similarity search based on Locality-Sensitive Filtering (LSF), generalizing the Indyk-Motwani (STOC 1998) Locality-Sensitive Hashing (LSH) framework to s…
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…
Generating k-independent variables in constant time
Tobias Christiani, Rasmus Pagh
The generation of pseudorandom elements over finite fields is fundamental to the time, space and randomness complexity of randomized algorithms and data structures. We consider the…