JHJakob Bæk Tejs Houen
Jakob Bæk Tejs Houen
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Jakob Bæk Tejs Houen has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Mikkel Thorup
BARC University of Copenhagen
2 shared publications - Mathias Bæk Tejs Knudsen
University of Copenhagen
1 shared publication - Søren Dahlgaard
University of Copenhagen
1 shared publication
Latest Publications
- Open Access
Fast Similarity Sketching
We consider the $\textit{Similarity Sketching}$ problem: Given a universe $[u] = \{0,\ldots, u-1\}$ we want a random function $S$ mapping subsets $A\subseteq [u]$ into vectors $S(A)$ of size $t$, such that similarity is preserved. More precisely: Given sets $A,B\subseteq [u]$, define $X_i = [S(A)[i] = S(B)[i]]$ and $X = \sum_{i\in [t]} X_i$. We want to have $E[X] = t\cdot J(A,B)$, where $J(A,B) = |A\cap B|/|A\cup B|$ and furthermore to have strong concentration guarantees (i.e. Chernoff-style bounds) for $X$. This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors $S(A)$ are also called $\textit{sketches}$. The seminal $t\times\textit{MinHash}$ algorithm uses $t$ random hash functions $h_1,\ldots, h_t$, and stores $\left ( \min_{a\in A} h_1(A),\ldots, \min_{a\in A} h_t(A) \right )$ as the sketch of $A$. The main drawback of MinHash is, however, its $O(t\cdot |A|)$ running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. Addressing this, Li et al.~[NIPS'12] introduced $\textit{one permutation hashing (OPH)}$, which creates a sketch of size $t$ in $O(t + |A|)$ time, but with the drawback that possibly some of the $t$ entries are ``empty'' when $|A| = O(t)$. One could argue that sketching is not necessary in this case, however the desire in most applications is to have $\textit{one}$ sketching procedure that works for sets of all sizes. Therefore, filling out these empty entries is the subject of several follow-up papers initiated by Shrivastava and Li~[ICML'14]. However, these ``densification'' schemes fail to provide good concentration bounds exactly in the case $|A| = O(t)$, where they are needed. (continued...)Open AccessFast Similarity Sketching
We consider the $\textit{Similarity Sketching}$ problem: Given a universe $[u] = \{0,\ldots, u-1\}$ we want a random function $S$ mapping subsets $A\subseteq [u]$ into vectors $S(A)$ of size $t$, such that similarity is preserved. More precisely: Given sets $A,B\subseteq [u]$, define $X_i = [S(A)[i] = S(B)[i]]$ and $X = \sum_{i\in [t]} X_i$. We want to have $E[X] = t\cdot J(A,B)$, where $J(A,B) = |A\cap B|/|A\cup B|$ and furthermore to have strong concentration guarantees (i.e. Chernoff-style bounds) for $X$. This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors $S(A)$ are also called $\textit{sketches}$. The seminal $t\times\textit{MinHash}$ algorithm uses $t$ random hash functions $h_1,\ldots, h_t$, and stores $\left ( \min_{a\in A} h_1(A),\ldots, \min_{a\in A} h_t(A) \right )$ as the sketch of $A$. The main drawback of MinHash is, however, its $O(t\cdot |A|)$ running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. Addressing this, Li et al.~[NIPS'12] introduced $\textit{one permutation hashing (OPH)}$, which creates a sketch of size $t$ in $O(t + |A|)$ time, but with the drawback that possibly some of the $t$ entries are ``empty'' when $|A| = O(t)$. One could argue that sketching is not necessary in this case, however the desire in most applications is to have $\textit{one}$ sketching procedure that works for sets of all sizes. Therefore, filling out these empty entries is the subject of several follow-up papers initiated by Shrivastava and Li~[ICML'14]. However, these ``densification'' schemes fail to provide good concentration bounds exactly in the case $|A| = O(t)$, where they are needed. (continued...) - Open Access
A Sparse Johnson-Lindenstrauss Transform using Fast Hashing
The \emph{Sparse Johnson-Lindenstrauss Transform} of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map $A \in \mathbb{R}^{m \times u}$ in $\ell_2$ that preserves distances up to distortion of $1 + \varepsilon$ with probability $1 - δ$, where $m = O(\varepsilon^{-2} \log 1/δ)$ and each column of $A$ has $O(\varepsilon m)$ non-zero entries. The previous analyses of the Sparse Johnson-Lindenstrauss Transform all assumed access to a $Ω(\log 1/δ)$-wise independent hash function. The main contribution of this paper is a more general analysis of the Sparse Johnson-Lindenstrauss Transform with less assumptions on the hash function. We also show that the \emph{Mixed Tabulation hash function} of Dahlgaard, Knudsen, Rotenberg, and Thorup (FOCS 2015) satisfies the conditions of our analysis, thus giving us the first analysis of a Sparse Johnson-Lindenstrauss Transform that works with a practical hash function.Open AccessA Sparse Johnson-Lindenstrauss Transform using Fast Hashing
The \emph{Sparse Johnson-Lindenstrauss Transform} of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map $A \in \mathbb{R}^{m \times u}$ in $\ell_2$ that preserves distances up to distortion of $1 + \varepsilon$ with probability $1 - δ$, where $m = O(\varepsilon^{-2} \log 1/δ)$ and each column of $A$ has $O(\varepsilon m)$ non-zero entries. The previous analyses of the Sparse Johnson-Lindenstrauss Transform all assumed access to a $Ω(\log 1/δ)$-wise independent hash function. The main contribution of this paper is a more general analysis of the Sparse Johnson-Lindenstrauss Transform with less assumptions on the hash function. We also show that the \emph{Mixed Tabulation hash function} of Dahlgaard, Knudsen, Rotenberg, and Thorup (FOCS 2015) satisfies the conditions of our analysis, thus giving us the first analysis of a Sparse Johnson-Lindenstrauss Transform that works with a practical hash function.