Topics in massive data summarization
Martin J. Strauss, Xuan Zheng · 2008
We consider three problems in this thesis. Two of them are about building near optimal histograms in non-uniform workload model and in probabilistic data streaming model respectively. The former has an associated weight vector with each streaming data vector, while the latter has a density function instead of a deterministic value as each data entry in the streaming data vector. The third one is to find approximate heavy hitters between two parties in a private model, in which, for every party no information is leaked unless necessary. More specifically, first, we want to construct a nearly workload-optimal histogram. Given B, we want to find the near optimal B bucket histogram under associated workload w within 1 + e error tolerance. In the cash register model where data is streamed as a series of updates, we can build a histogram using polylogarithmic space, polylogarithmic time to process each item, and polylogarithmic post-processing time to build the histogram. All these results need the workload to be explicitly stored since we show that if the workload is summarized in small space lossily, algorithmic results such as above do not exist. Then, we consider the problem of private computation of approximate Heavy Hitters. Alice and Bob each hold a vector and, in the vector sum, they want to find the B largest values along with their indices. We show how to solve the problem privately with polylogarithmic communication, polynomial work and constantly many rounds in the sense that nothing is learned by Alice and Bob beyond what is implied by their input, the ideal top-B output, and goodness of approximation (equivalently, the Euclidean norm of the vector sum). We give lower bounds showing that the Euclidean norm must leak by any efficient algorithm. In the third problem, we want to build a near optimal histogram on probabilistic data streams. Given B, we want to find the near optimal B bucket histogram on probabilistic data streams under both L1 measurement and L2 measurement. We give deterministic algorithms without sampling. We can build histograms using poly-logarithmic space, polylogarithmic time to process each item, and polylogarithmic post-processing time to build the histogram. The result we give under L2 measurement is within (1 + e)-error tolerance, and the result under L1 measurement is heuristic. We also give a direction to give guarantees to the heuristic.