Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in mathbb RdRd

摘要

We present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles (cells) in , for any d > 0. Our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. Our algorithm makes 2 + 1 passes, for any > 0, and requires memory at most . This exhibits a strong memory-space tradeoff: a few more passes significantly lowers its memory requirements, thus trading one of the two most important resources in streaming computation for the other. Chang and Kannan ? first considered this problem for [1] d = 1, 2. Our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but practical computation with such large inputs requires very restricted models of computation.