Abstract
We introduce Density sketches (DS): a succinct online summary of the data distribution. DS can accurately estimate point wise probability density. Interestingly, DS also provides a capability to sample unseen novel data from the underlying data distribution. Thus, analogous to popular generative models, DS allows us to succinctly replace the real-data in almost all machine learning pipelines with synthetic examples drawn from the same distribution as the original data. However, unlike generative models, which do not have any statistical guarantees, DS leads to theoretically sound asymptotically converging consistent estimators of the underlying density function. Density sketches also have many appealing properties making them ideal for large-scale distributed applications. DS construction is an online algorithm. The sketches are additive, i.e., the sum of two sketches is the sketch of the combined data. These properties allow data to be collected from distributed sources, compressed into a density sketch, efficiently transmitted in the sketch form to a central server, merged, and re-sampled into a synthetic database for modeling applications. Thus, density sketches can potentially revolutionize how we store, communicate, and distribute data.
Introduction
In statistical estimation, researchers often face a trade-off between statistical guarantees, scalability, and generative capability. Traditional non-parametric methods like Histograms and Kernel Density Estimators (KDE) offer consistency—converging to the true distribution as data increases—but suffer from the "curse of dimensionality," where memory requirements grow exponentially with dimensions. Conversely, modern generative models like GANs and VAEs excel at sampling but lack rigorous statistical guarantees.
Density Sketches (DS) address this gap by providing a summary that is succinct, online, mergeable, and generative. By leveraging probabilistic data structures, DS enables accurate density estimation and synthetic data generation while maintaining a small memory footprint suitable for edge devices and distributed systems.
Methodology
The core of the Density Sketch is the integration of histogram logic with efficient streaming algorithms. Instead of a full high-dimensional array, DS utilizes a Count Sketch—a probabilistic structure that uses hash functions to map bin IDs into a small 2D array, keeping memory usage logarithmic relative to the number of bins.
To handle the sparsity of high-dimensional data, DS employs an augmented min-heap to track "heavy hitters," or the most populated bins. As data streams in, the algorithm identifies the relevant bin, updates the Count Sketch, and adjusts the heap if the bin's count becomes significant. Sampling is achieved by selecting a bin from the heap (weighted by estimated count) and performing uniform sampling within its boundaries. Crucially, because Count Sketches are additive, sketches from distributed sources can be merged by simple summation.
Evaluation and Results
The authors evaluated DS on several large-scale datasets, including Skin/Nonskin (180k samples), SUSY (4.5M samples), Higgs (10M samples), and MNIST.
Key findings include:
- Massive Compression: DS achieved up to 200x compression on the Skin dataset and 50x on the 2.5GB Higgs dataset while maintaining comparable classification accuracy.
- Downstream Performance: Models trained on synthetic data from DS performed nearly as well as those trained on raw data, outperforming random sampling at equivalent memory scales.
- Distribution Capture: The sketch effectively captures the essential structure of the distribution. For example, samples from an MNIST-based DS were clearly recognizable as digits.
The "capture ratio" ($ratio_h$) of the heap determines performance; when data is highly clustered, the heap captures most of the distribution, allowing the sketch to rival a full histogram in accuracy.
Discussion and Future Work
While DS effectively bypasses the exponential memory cost for sparse data, it faces challenges when data is extremely scattered, as seen in high-dimensional datasets like Webspam (254 dimensions). Future improvements may involve data-dependent partitioning schemes to replace regular grids. Additionally, while sketching provides inherent abstraction, integrating formal Differential Privacy guarantees remains a promising direction for enhancing data security in distributed applications.
Summary updated