3 papers
cs.DS2019
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 , $α…
cs.DS2019
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…
cs.DS2017
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…