1 citations · 2 across the 5 of their papers we have counts for
8 papers
Huffman-Bucket Sketch: A Simple Algorithm for Cardinality Estimation
Matti Karppa
We introduce the Huffman-Bucket Sketch (HBS), a simple, mergeable data structure that losslessly compresses a HyperLogLog (HLL) sketch with registers to optimal space $O(m+\log…
Engineering Compressed Matrix Multiplication with the Fast Walsh-Hadamard Transform
Joel Andersson, Matti Karppa
We present an implementation of Pagh's compressed matrix multiplication algorithm, a randomized algorithm that constructs sketches of matrices to compute an unbiased estimate of th…
HyperLogLogLog: Cardinality Estimation With One Log More
Matti Karppa, Rasmus Pagh
We present HyperLogLogLog, a practical compression of the HyperLogLog sketch that compresses the sketch from bits down to $m \log_2\log_2\log_2 m + O(m+\log\log n)…
DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
Matti Karppa, Martin Aumüller, Rasmus Pagh
Kernel Density Estimation (KDE) is a nonparametric method for estimating the shape of a density function, given a set of samples from the distribution. Recently, locality-sensitive…
Engineering Boolean Matrix Multiplication for Multiple-Accelerator Shared-Memory Architectures
Matti Karppa, Petteri Kaski
We study the problem of multiplying two bit matrices with entries either over the Boolean algebra or over the binary field . We engineer high-per…
An adaptive prefix-assignment technique for symmetry reduction
Tommi Junttila, Matti Karppa, Petteri Kaski +1
This paper presents a technique for symmetry reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwis…
Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
Matti Karppa, Petteri Kaski, Jukka Kohonen +1
We derandomize G. Valiant's [J. ACM 62 (2015) Art. 13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic s…
A faster subquadratic algorithm for finding outlier correlations
Matti Karppa, Petteri Kaski, Jukka Kohonen
We study the problem of detecting outlier pairs of strongly correlated variables among a collection of variables with otherwise weak pairwise correlations. After normalization,…