2014/04/18 by Konstantin Kutzkov, Rasmus Pagh, Kutzkov, Konstantin +1
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1404.4693
To appear in SWAT 2014
arxiv created 2014/04/18 · openalex publication_date 2014/04/18 · arxiv updated 2014/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consistent sampling is a technique for specifying, in small space, a subset S of a potentially large universe U such that the elements in S satisfy a suitably chosen sampling condition. Given a subset I⊆ U it should be possible to quickly compute I∩ S, i.e., the elements in I satisfying the sampling condition. Consistent sampling has important applications in similarity estimation, and estimation of the number of distinct items in a data stream. In this paper we generalize consistent sampling to the setting where we are interested in sampling size-k subsets occurring in some set in a collection of sets of bounded size b, where k is a small integer. This can be done by applying standard consistent sampling to the k-subsets of each set, but that approach requires time Θ(bk). Using a carefully designed hash function, for a given sampling probability p ∈ (0,1], we show how to improve the time complexity to Θ(b\lceil k/2\rceillog log b + pbk) in expectation, while maintaining strong concentration bounds for the sample. The space usage of our method is Θ(b\lceil k/4\rceil). We demonstrate the utility of our technique by applying it to several well-studied data mining problems. We show how to efficiently estimate the number of frequent k-itemsets in a stream of transactions and the number of bipartite cliques in a graph given as incidence stream. Further, building upon a recent work by Campagna et al., we show that our approach can be applied to frequent itemset mining in a parallel or distributed setting. We also present applications in graph stream mining.