Tracking and approximating data matrices in streaming fashion is a fundamental challenge. The problem requires more care and attention when data comes from multiple distributed sites, each receiving a stream of data. This paper considers the problem of "tracking approximations to a matrix" in the distributed streaming model. In this model, there are m distributed sites each observing a distinct stream of data (where each element is a row of a distributed matrix) and has a communication channel with a coordinator, and the goal is to track an eps-approximation to the norm of the matrix along any direction. To that end, we present novel algorithms to address the matrix approximation problem. Our algorithms maintain a smaller matrix B, as an approximation to a distributed streaming matrix A, such that for any unit vector x: | ||A x||^2 - ||B x||^2 | <= eps ||A||_F^2. Our algorithms work in streaming fashion and incur small communication, which is critical for distributed computation. Our best method is deterministic and uses only O((m eps) log(beta N)) communication, where N is the size of stream (at the time of the query) and beta is an upper-bound on the squared norm of any row of the matrix. In addition to proving all algorithmic properties theoretically, extensive experiments with real large datasets demonstrate the efficiency of these protocols.
Later, Huang al @cite_25 proposed a randomized algorithm that uses @math space at each site and @math total communication and tracks heavy hitters in a distributed stream. For each item @math in the stream a site chooses to send a message with a probability @math where @math is a @math -approximation of the total count. It then sends @math the total count of messages at site @math where @math , to the coordinator. Again an approximation heavy-hitter count @math can be used at each site to reduce space.
@cite_25
2949236774
We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the count-tracking problem, where there are @math players, each holding a counter @math that gets incremented over time, and the goal is to track an @math -approximation of their sum @math continuously at all times, using minimum communication. While the deterministic communication complexity of the problem is @math , where @math is the final value of @math when the tracking finishes, we show that with randomization, the communication cost can be reduced to @math . Our algorithm is simple and uses only O(1) space at each player, while the lower bound holds even assuming each player has infinite computing power. Then, we extend our techniques to two related distributed tracking problems: frequency-tracking and rank-tracking , and obtain similar improvements over previous deterministic algorithms. Both problems are of central importance in large data monitoring and analysis, and have been extensively studied in the literature.