Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data
Authors:
Open Access
- 20 April 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1739-1749
Abstract
Kernel density estimation is a simple and effective method that lies at the heart of many important machine learning applications. Unfortunately, kernel methods scale poorly for large, high dimensional datasets. Approximate kernel density estimation has a prohibitively high memory and computation cost, especially in the streaming setting. Recent sampling algorithms for high dimensional densities can reduce the computation cost but cannot operate online, while streaming algorithms cannot handle high dimensional datasets due to the curse of dimensionality. We propose RACE, an efficient sketching algorithm for kernel density estimation on high-dimensional streaming data. RACE compresses a set of N high dimensional vectors into tiny arrays of integer counters. These arrays are sufficient to estimate the kernel density for a large class of kernels. Our one-pass sketch is simple to implement and comes with strong theoretical guarantees. We evaluate our method on real-world high-dimensional datasets and show that our sketch achieves 10x better compression compared to existing methods.1Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Generalized Outlier Detection with Flexible Kernel Density Estimates2014
- Mergeable summariesACM Transactions on Database Systems, 2013
- Multivariate Density Estimation by Bayesian Sequential PartitioningJournal of the American Statistical Association, 2013
- Taylor expansion of the inverse function with application to the Langevin functionMathematics and Mechanics of Solids, 2012
- Density‐based clusteringWIREs Data Mining and Knowledge Discovery, 2011
- The Sequence Read ArchiveNucleic Acids Research, 2010
- Outlier Detection with Kernel Density Functions2007
- DENCLUE 2.0: Fast Clustering Based on Kernel Density Estimation2007
- Density Estimation for Spatial Data Streams2005
- Mode-finding for mixtures of Gaussian distributionsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000