On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch
Barna Saha, Lise Getoor · 2009
We generalize the graph streaming model to hypergraphs. In this streaming model, hyperedges are arriving online and any computation has to be done on-the-fly using a small amount of space. Each hyperedge can be viewed as a set of elements (nodes), so we refer to our proposed model as the “set-streaming” model of computation. We consider the problem of “maximum coverage”, in which k sets have to be selected that maximize the total weight of the covered elements. In the set-streaming model of computation, we show that our algorithm for maximum-coverage achieves an approximation factor of ¼. When multiple passes are allowed, we also provide a ⊖(log n) approximation algorithm for the set-cover. We next consider a multi-topic blog-watch application, an extension of blog-alert like applications for handling simultaneous multiple-topic requests. We show how the problems of maximum-coverage and set-cover in the set-streaming model can be utilized to give efficient online solutions to this problem. We verify the effectiveness of our methods both on synthetic and real weblog data.