8 citations · 8 across the 3 of their papers we have counts for
5 papers · 1 filter
The space complexity of inner product filters
Rasmus Pagh, Johan Sivertsen
Motivated by the problem of filtering candidate pairs in inner product similarity joins we study the following inner product estimation problem: Given parameters , $α…
Similarity Problems in High Dimensions
Johan von Tangen Sivertsen
The main contribution of this dissertation is the introduction of new or improved approximation algorithms and data structures for several similarity search problems. We examine th…
Fast Nearest Neighbor Preserving Embeddings
Johan Sivertsen
We show an analog to the Fast Johnson-Lindenstrauss Transform for Nearest Neighbor Preserving Embeddings in . These are sparse, randomized embeddings that preserve the (app…
Approximate Furthest Neighbor with Application to Annulus Query
Rasmus Pagh, Francesco Silvestri, Johan Sivertsen +1
Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider approximate furthest neighbor (AFN) queries…
Distance Sensitive Bloom Filters Without False Negatives
Mayank Goswami, Rasmus Pagh, Francesco Silvestri +1
A Bloom filter is a widely used data-structure for representing a set and answering queries of the form "Is in ?". By allowing some false positive answers (saying "yes"…