Kernel Density Estimation (KDE) is a nonparametric method for estimatig the shape of a density function, given a set of samples from the distribution. Recently, locality-sensitive hashing, originally proposed as a tool for nearest neighbor search, has been shown to enable fast KDE data structures. However, these approaches do not take advantage of the many other advances that have been made in algorithms for nearest neighbor algorithms. We present an algorithm called Density Estimation from Approximate Nearest Neighbors (DEANN) where we apply Approximate Nearest Neighbor (ANN) algorithms as a black box subroutine to compute an unbiased KDE. The idea is to find points that have a large contribution to the KDE using ANN, compute their contribution exactly, and approximate the remainder with Random Sampling (RS). We present a theoretical argument that supports the idea that an ANN subroutine can speed up the evaluation. Furthermore, we provide a C++ implementation with a Python interface that can make use of an arbitrary ANN implementation as a subroutine for KDE evaluation. We show empirically that our implementation outperforms state of the art implementations in all high dimensional datasets we considered, and matches the performance of RS in cases where the ANN yield no gains in performance.

We present HyperLogLogLog, a practical compression of the HyperLogLog sketch that compresses the sketch from $O(młogłog n)$ bits down to $m łog_2łog_2łog_2 m + O(m+łogłog n)$ bits for estimating the number of distinct elements~n using m~registers. The algorithm works as a drop-in replacement that preserves all estimation properties of the HyperLogLog sketch, it is possible to convert back and forth between the compressed and uncompressed representations, and the compressed sketch maintains mergeability in the compressed domain. The compressed sketch can be updated in amortized constant time, assuming n is sufficiently larger than m. We provide a C++ implementation of the sketch, and show by experimental evaluation against well-known implementations by Google and Apache that our implementation provides small sketches while maintaining competitive update and merge times. Concretely, we observed approximately a 40% reduction in the sketch size. Furthermore, we obtain as a corollary a theoretical algorithm that compresses the sketch down to $młog_2łog_2łog_2łog_2 m+O(młogłogłog m/łogłog m+łogłog n)$ bits.

Abstract We derandomize Valiant’s (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant’s randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders by Reingold et al. (Ann Math 155(1):157–187, 2002). We say that a function $$f:\{-1,1\}^d\rightarrow \{-1,1\}^D$$ f : { - 1 , 1 } d → { - 1 , 1 } D is a correlation amplifier with threshold $$0\le \tau \le 1$$ 0 ≤ τ ≤ 1 , error $$\gamma \ge 1$$ γ ≥ 1 , and strength p an even positive integer if for all pairs of vectors $$x,y\in \{-1,1\}^d$$ x , y ∈ { - 1 , 1 } d it holds that (i) $$|\langle x,y\rangle |<\tau d$$ | ⟨ x , y ⟩ | < τ d implies $$|\langle f(x),f(y)\rangle |\le (\tau \gamma )^pD$$ | ⟨ f ( x ) , f ( y ) ⟩ | ≤ ( τ γ ) p D ; and (ii) $$|\langle x,y\rangle |\ge \tau d$$ | ⟨ x , y ⟩ | ≥ τ d implies $$\left (\frac{\langle x,y\rangle }{\gamma d}\right )^pD \le \langle f(x),f(y)\rangle \le \left (\frac{\gamma \langle x,y\rangle }{d}\right )^pD$$ ⟨ x , y ⟩ γ d p D ≤ ⟨ f ( x ) , f ( y ) ⟩ ≤ γ ⟨ x , y ⟩ d p D .

We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor 〈2, 2, 2〉 that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)], we show that the probabilistic tensor rank and border rank satisfy By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs. Our algorithms are opportunistic in the sense that their worst-case scaling is essentially governed by the probabilistic rank, yet their result is accumulated through independent repetitions, where the partial result can be inspected at each repeat for possible early termination, and each repeat scales according to the rank of the outcome-tensors. For example, representing 〈2, 2, 2〉 probabilistically using an ensemble of tensors of rank 6, we obtain an algorithm that, with high probability, multiplies two 2d × 2d Boolean matrices in operations. This algorithm consists of independent repeats that each run in O(6d) operations and enable inspection of the partial result at each repeat. Analogously, a probabilistic representation of 〈2, 2, 2〉 using tensors of border rank 5 gives an algorithm that runs in operations, consisting of repeats that run in Õ(5d) operations each. Asymptotically, we use Adleman's argument to show that, over the complex field, the support rank exponent ωs of matrix multiplication [H. Cohn and C. Umans, SODA’12] gives the lower bound for probabilistic tensor rank. While this enables an approach to obtaining asymptotically faster algorithm designs for matrix multiplication via the Cohn–Umans inequality , the main motivation for the present paper is to enable an approach towards fast practical algorithms using small probabilistic tensors.

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d , and for some constants 0<τ < ρ < 1, we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value. Improving on an algorithm of Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ({ −1,1}-valued data normalized to unit Euclidean length) runs in time Õ(( n max,{ 1−γ + M (Δ γ ,γ), M (1−γ ,2 Δ γ)} + qdn 2γ ), where 0<γ < 1 is a constant tradeoff parameter and M (μ, ν) is the exponent to multiply an ⌊ n μ ⌋ × ⌊ n ν ⌋ matrix with an ⌊ n ν ⌋ × ⌊ n μ ⌋ matrix and Δ =1/(1−log τ ρ). As corollaries we obtain randomized algorithms that run in time Õ( ( n 2/ω 3−log τ ρ + qdn 2/(1−log τ ρ)3=log ττ ρ ) and in time õ( ( n 4 / 2+α (1−log τ ρ) + qdn 2/α (1−log τ ρ)2+α (1−log τ ρ) >), where 2≤ ω <2.38 is the exponent for square matrix multiplication and 0.3<α ≤ 1 is the exponent for rectangular matrix multiplication. The notation Õ(ṡ) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ. We present further corollaries for the light bulb problem and for learning sparse Boolean functions.

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 pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework (McKay, 1998). Among key features of the technique are (i) adaptability—the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries; (ii) parallelizability—prefix-assignments can be processed in parallel independently of each other; (iii) versatility—the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph; and (iv) implementability—the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface.

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value for some constants 0 < τ < ρ < 1. Improving on an algorithm of G. Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ({–1, 1}-valued data normalized to unit Euclidean length) runs in time where 0 < γ < 1 is a constant tradeoff parameter and M(μ, v) is the exponent to multiply an ⌊nμ⌋ × ⌊nv⌋ matrix with an ⌊nv⌋ × ⌊nμ⌋ matrix and Δ = 1/(1 – logτ ρ). As corollaries we obtain randomized algorithms that run in time and in time where 2 ≤ ω < 2.38 is the exponent for square matrix multiplication and 0.3 < α ≤ 1 is the exponent for rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation Õ(·) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ.)

Handshape has an important role in sign languages. It would be inconceivable to try to understand sign language without recognising the handshapes. Over the years, numerous different approaches have been proposed for extracting the hand configuration information. The existing approaches for hand-shape recognition have problems especially with the huge sizes of modern linguistic corpora. Computationally expensive methods become easily infeasible with such large amounts of data. In this paper we examine the straightforward and efficient approach of recognising handshapes by our existing image category detection methodology, involving state-of-the-art local image descriptors. In the experiments the approach produces promising results. On the image feature side, we find that surprisingly complex hierarchical descriptors of shape primitive statistics provide the best overall performance in hand shape recognition. The accuracy of feature-wise detections can be improved by fusing together several features. Considering the temporal succession of the hand blobs markedly improves the accuracy over detecting the hand shape in each video frame in isolation.