The k-Minimum Values (KMV) data sketch algorithm stores the k least hash keys generated by hashing the items in a dataset. We show that compression based on ordering the keys and encoding successive differences can offer O(log n) bits per key in expected storage savings, where n is the number of unique values in the data set. We also show that O(log n) expected bits saved per key is optimal for any form of compression for the k least of n random values – that the encoding method is near-optimal among all methods to encode a KMVsketch.We present a practical method to perform that compression, show that it is computationally efficient, and demonstrate that its average savings in practice is within about five percent of the theoretical minimum based on entropy. We verify that our method outperforms off-the-shelf compression methods, and we demonstrate that it is practical, using real and synthetic data.1

Data sketching has emerged as a key infrastructure for large-scale data analysis on streaming and distributed data. Merging sketches enables efficient estimation of cardinalities and frequency histograms over distributed data. However, merging sketches can require that each sketch stores hash codes for identifiers in different data sets or partitions, in order to perform effective matching. This can reveal identifiers during merging or across different data set or partition owners. This paper presents a framework to use noisy hash codes, with the noise level selected to obfuscate identifiers while allowing matching, with high probability. We give probabilistic error bounds on simultaneous obfuscation and matching, concluding that this is a viable approach.

Given an $n \times d$ dimensional dataset A, a projection query specifies a subset $C \subseteq [d]$ of columns which yields a new $n \times |C|$ array. We study the space complexity of computing data analysis functions over such subspaces, including heavy hitters and norms, when the subspaces are revealed only after observing the data. We show that this important class of problems is typically hard: for many problems, we show $2^Ømega(d) $ lower bounds. However, we present upper bounds which demonstrate space dependency better than $2^d$. That is, for $c,c' \in (0,1)$ and a parameter $N=2^d$ an $N^c$-approximation can be obtained in space $\min(N^c', n)$, showing that it is possible to improve on the naï ve approach of keeping information for all $2^d$ subsets of d columns. Our results are based on careful constructions of instances using coding theory and novel combinatorial reductions that exhibit such space-approximation tradeoffs.